题意：
给出一个n个结点m条边有向图，可能有负权边；
但是存在负权边a->b则不会有某个路径可以从b到a；
求一个源点s到所有点的最短路(无解输出"NO PATH")；
n<=25000，，m<=150000；
题解：
高高兴兴的写了一发spfa，O(km)嘛；
然后就TLE了，这题丧心病狂的把spfa卡掉了；
这时候理所当然的想到了dij+heap，写到一半想起来不支持负权边；
所以这个不是一个简单的单源最短路问题；
题中有一个重要条件就是负权边不会回去；
我本以为只是排除了负权环的存在，但是事实上，这个性质使负权边不可能在强连通分量内；
那么每个强连通分量内的最短路可以用dij实现；
强连通分量缩点后是DAG，直接DP传一下进入强连通分量的最短路就可以了；
时间复杂度O(nlogn)；
HINT：
每次dij时是没有源点的，直接将所有点加入heap做最短路；
不可到达的强连通分量不能将最短路下传，防止在最后判断是否为inf时错误；
USACO数据还是naive；
为了写这题还去学了dij+heap然后过不了也是醉；
最近写的代码越来越长是错觉吗。。。
代码：
#include<queue>#include<stack>#include<vector>#include<stdio.h>#include<string.h>#include<algorithm>#define N 25500#define pr pair<int,int>using namespace std;vector<int>to[N],val[N],son[N];priority_queue<pr,vector<pr >,greater<pr > >poq;queue<int>q;stack<int>st;int f[N],dis[N];int deep[N],low[N],belong[N],in[N],cnt,tot;bool ins[N],cov[N],vis[N];void tarjan(int x){deep[x]=low[x]=++cnt;st.push(x),ins[x]=1;int i,y;for(i=0;i<to[x].size();i++){if(!deep[y=to[x][i]])tarjan(y),low[x]=min(low[x],low[y]);else if(ins[y])low[x]=min(low[x],deep[y]);}if(deep[x]==low[x]){tot++;int k;do{k=st.top(),st.pop();ins[k]=0;belong[k]=tot;son[tot].push_back(k);}while(k!=x);}}void dij(int x){int i,j,k,y;for(i=0;i<son[x].size();i++)poq.push(pr(dis[son[x][i]],son[x][i]));while(!poq.empty()){k=poq.top().second;poq.pop();if(vis[k])continue;vis[k]=1;for(i=0;i<to[k].size();i++){if(belong[y=to[k][i]]==x)if(dis[y]>dis[k]+val[k][i]){dis[y]=dis[k]+val[k][i];poq.push(pr(dis[y],y));}}}}int main(){int n,m1,m2,s,i,j,k,x,y,v;scanf("%d%d%d%d",&n,&m1,&m2,&s);for(i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);to[x].push_back(y);val[x].push_back(v);to[y].push_back(x);val[y].push_back(v);}for(i=1;i<=m2;i++){scanf("%d%d%d",&x,&y,&v);to[x].push_back(y);val[x].push_back(v);}for(i=1;i<=n;i++)if(!deep[i])tarjan(i);for(x=1;x<=n;x++){for(i=0;i<to[x].size();i++){if(belong[y=to[x][i]]!=belong[x]){in[belong[y]]++;}}}for(i=1;i<=tot;i++)if(!in[i])q.push(i);memset(dis,0x3f,sizeof(dis));dis[s]=0,cov[belong[s]]=1;while(!q.empty()){x=q.front(),q.pop();if(cov[x])dij(x);for(j=0;j<son[x].size();j++){k=son[x][j];for(i=0;i<to[k].size();i++){if(belong[y=to[k][i]]!=x){if(cov[x]){cov[belong[y]]=1;dis[y]=min(dis[k]+val[k][i],dis[y]);}in[belong[y]]–;if(!in[belong[y]])q.push(belong[y]);}}}}for(i=1;i<=n;i++){if(dis[i]==0x3f3f3f3f)puts("NO PATH");elseprintf("%d\n",dis[i]);}return 0;}
去了不同的地方，看了不同的风景，知道了不同的事，
