http://poj.org/problem?id=3114
题意：给出m条边及其权，询问x y ，如果x,y在同一个强连通分量中，输出0，否则输出两点所在强连通分量的最短路径。
思路：tarjan缩点 最短路。
思路不难，关键是仔细。
#include #include #include #include #include #include using namespace std;const int maxn = 505;const int INF = 0x3f3f3f3f;struct node{int v,w;};vector edge[maxn];//原图vector edge2[maxn];//缩点后的图stackst;int n,m,k;int vis[maxn],instack[maxn],dfn[maxn],low[maxn],dep;int scc,set[maxn];int dis[maxn];void init(){for(int i = 1; i <= n; i++){edge[i].clear();edge2[i].clear();}memset(vis,0,sizeof(vis));memset(instack,0,sizeof(instack));memset(dfn,0,sizeof(vis));memset(low,0,sizeof(vis));while(!st.empty()) st.pop();dep = 0;scc = 0;}void tarjan(int u){dfn[u] = low[u] = ++dep;st.push(u);instack[u] = 1;vis[u] = 1;for(int i = 0; i <(int)edge[u].size(); i++){int v = edge[u][i].v;if(!vis[v]){tarjan(v);low[u] = min(low[u],low[v]);}else if(instack[v])low[u] = min(low[u],dfn[v]);}if(low[u] == dfn[u]){scc += 1;//强连通分量数加1while(1){int t = st.top();st.pop();instack[t] = 0;set[t] = scc;//记录t属于哪个强连通分量if(t == u)break;}}}//缩点建图void creat_DAG(){for(int u = 1; u <= n; u++){for(int i = 0; i <(int)edge[u].size(); i++){int v = edge[u][i].v;int w = edge[u][i].w;if(set[u] != set[v])edge2[ set[u] ].push_back((struct node){set[v], w});}}}void spfa(int s){queueque;int inque[maxn];while(!que.empty()) que.pop();memset(inque,0,sizeof(inque));for(int i = 1; i <= scc; i++)dis[i] = INF;dis[s] = 0;inque[s] = 1;que.push(s);while(!que.empty()){int u = que.front();que.pop();inque[u] = 0;for(int i = 0; i <(int)edge2[u].size(); i++){int v = edge2[u][i].v;if(dis[v] > edge2[u][i].w + dis[u]){dis[v] = dis[u] + edge2[u][i].w;if(!inque[v]){inque[v] = 1;que.push(v);}}}}}int main(){while(~scanf("%d %d",init();int u,v,w;while(m--){scanf("%d %d %d",edge[u].push_back((struct node){v,w});}for(int i = 1; i <= n; i++)if(!vis[i])tarjan(i);creat_DAG();scanf("%d",while(k--){scanf("%d %d",int uu = set[u];int vv = set[v];if(uu == vv){printf("0\n");continue;}if(edge2[uu].size() == 0){printf("Nao e possivel entregar a carta\n");continue;}spfa(uu);if(dis[vv] == INF)printf("Nao e possivel entregar a carta\n");else printf("%d\n",dis[vv]);}printf("\n");}return 0;}