http://poj.org/problem?id=3114
题意:给出m条边及其权值,询问x y ,如果x,y在同一个强连通分量中,输出0,否则输出两点所在强连通分量的最短路径。
思路:tarjan缩点 + 最短路。
思路不难,关键是仔细。
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <stack> #include <queue> using namespace std; const int maxn = 505; const int INF = 0x3f3f3f3f; struct node { int v,w; }; vector <struct node> edge[maxn];//原图 vector <struct node> edge2[maxn];//缩点后的图 stack<int>st; 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;//强连通分量数加1 while(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) { queue<int>que; 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",&n,&m)) { if(n == 0 && m == 0) break; init(); int u,v,w; while(m--) { scanf("%d %d %d",&u,&v,&w); edge[u].push_back((struct node){v,w}); } for(int i = 1; i <= n; i++) if(!vis[i]) tarjan(i); creat_DAG(); scanf("%d",&k); while(k--) { scanf("%d %d",&u,&v); 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; }