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;
}