自己写的不知道哪里wa了，明明和网上的代码差不多。，。
/*
给定一张图，有的边是无向边，有的是有向边，有向边不会出现在环中，且有可能是负权值
现在给定起点s，求出s到其余所有点的最短路长度
任何存在负权边的图都不可以用dij（有向图，无向图，有环图，无环图）
比如(1,2,8),(1,3,10)(3,2,-5),显然1-3的最短路径是5，但是dij求出的就是8
并且spfa超时 利用本题的无向边无 负权，且单向边不会出现在环中，先再每个联通块内求dij，然后用拓扑排序处理联通块之间的距离
先将所有无向边加入图，然后求出所有联通块，将联通块缩点
然后再加入有向边，按拓扑排序进行
算法流程：
1.把双向边加入图中，确定所有联通块，并染色
2.把单向边加入图中，确定所有的联通块的出度入度，只有S所在的联通块入度为0情况下才有解
3.开始拓扑排序，初始队列q中仅有c[S]联通块，同时建立dist数组，dist[s]=0
4.不断取出队头联通块，在联通块内进行堆优化的dij
a.把联通块内的所有结点加入堆
b.从堆中取出d[x]最小的结点，若x已经在最短路集合中，continue
c.遍历x的所有边(x,y,z),进行松弛
如果y是联通块内的，并且y被更新，则把y插入堆中
若y是其他联通块的，那么in[c[y]]--,如果减到了0，就把c[y]加入队尾
*/
#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
#define maxn 25005
#define maxm 50005
#define ll long long
struct Edge{int to,nxt,w,flag;}edge[maxm<<];
int head[maxn],tot,in[maxn],t,r,p,s;
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v,int w,int flag){
edge[tot].to=v;edge[tot].w=w;edge[tot].flag=flag;
edge[tot].nxt=head[u];head[u]=tot++;
} int c[maxn],cnt;
vector<int>vec[maxn];
void dfs(int u){//染色
c[u]=cnt;
vec[cnt].push_back(u);
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(c[v]==)dfs(v);
}
} int d[maxn],vis[maxn],used[maxn];
int main(){
while(cin>>t>>r>>p>>s){
init();
int u,v,w;
for(int i=;i<=r;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w,);
addedge(v,u,w,);
} memset(c,,sizeof c);
for(int i=;i<=t;i++)
if(!c[i]){
cnt++;
vec[cnt].clear();
dfs(i);
} memset(in,,sizeof in);
for(int i=;i<=r;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w,);
in[c[v]]++;
} memset(d,,sizeof d);
memset(used,,sizeof used);
memset(vis,,sizeof vis);
d[s]=; queue<int>q;
q.push(c[s]);//把s所在联通块入队
priority_queue<pair<int,int> >pq;
while(!q.empty()){
int u=q.front();q.pop();//从队头取出联通块
for(int i=;i<vec[u].size();i++){
int v=vec[u][i];
pq.push(make_pair(-d[v],v));
}
while(!pq.empty()){
int x=pq.top().second;pq.pop();
if(vis[x])continue;
vis[x]=;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to,z=edge[i].w;
if(d[y]>d[x]+z){
if(c[x]==c[y]){
d[y]=d[x]+z;
pq.push(make_pair(-d[y],y));
}
}
if(c[x]!=c[y]){
d[y]=min(d[x]+z,d[y]);
in[c[y]]--;
if(in[c[y]]==)
q.push(c[y]);
}
}
}
}
for(int i=;i<=t;i++)
if(d[i]>0x3f3f3f3f)puts("NO PATH");
else printf("%d\n",d[i]);
}
}
网上的
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N = ,M = , INF=0x3f3f3f3f; // M为双向边加单向边
int T,R,P,S,d[N];
int head[N],Next[M],ver[M],edge[M],tot;
bool v[N];
int c[N],totc,deg[N];
queue<int> q; // 联通块的拓扑序
priority_queue<pair<int, int> > Q; // Dij
void add(int x,int y, int z){
ver[++tot]=y, edge[tot]=z;
Next[tot]=head[x], head[x]=tot;
}
void dfs(int x){
for(int i=head[x]; i; i=Next[i]){
int y = ver[i];
if(!c[y]){
c[y]=totc;
dfs(y);
}
}
}
void Dijkstra(){
while(Q.size()){
int x = Q.top().second; Q.pop();
if(v[x])continue;
v[x] = ;
for(int i=head[x]; i; i=Next[i]){
int y = ver[i], wei = edge[i];
if(d[y] > d[x]+wei){
d[y] = d[x]+wei;
if(c[y]==c[x]) Q.push(make_pair(-d[y], y));
}
// 对遍历到的点，判断是否不同联通块
// 联通块入度减少，并且判0
if(c[x]!=c[y] && !--deg[c[y]])q.push(c[y]);
}
}
}
int main(){
cin>>T>>R>>P>>S;
int x,y,z;
fo(i,,R){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
// 划分联通块
fo(i,,T){
if(!c[i]){
c[i]=++totc;
dfs(i);
}
}
fo(i,,P){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
++deg[c[y]]; // 联通块的入度
}
// 联通块之间进行拓扑排序
q.push(c[S]); // 先加入起点
fo(i,,totc)if(!deg[i])q.push(i); // 加入0度的联通块
// topsort
memset(d, , sizeof(d)); // 这里最大值不能为0x3f,0x7f对应127
d[S] = ;
while(q.size()){
int i = q.front(); q.pop();
fo(j,,T)
if(c[j]==i)
Q.push(make_pair(-d[j], j)); // 联通块
Dijkstra();
}
fo(i,,T){
if(d[i]>INF)puts("NO PATH");
else printf("%d\n",d[i]);
}
}