3 、空间活动
【题目描述】
贝茜和佩奇正在玩一款游戏，在游戏开始会生成一个有n个点m条单向边的地图，经过每条边需要花费价格为Hi的费用（Hi<=1000）。但是如果两个点可以互相到达，那么这两个点之间需要花费的价格就变为0。总共有k关，每一关会给你两个点a，b（0< a，b <=n），让你求从a走到b的最小花费。
【输入格式】
第一行三个数n，m，k；
接下来m行每行三个数，x,y,Hi表示存在一条（x，y）的单向边，边权为Hi；
接下来k行每行两个数a，b。
【输出格式】
k行，每行一个数表示从a走到b的最小花费（如果不能从a走到b，那么输出“No”）。
【样例输入】
4 5 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
1 2
1 3
1 4
4 3
4 1
【样例输出】
0
6
6
0
No
【数据范围】
对于30%的数据n<=20，k<=1;
对于另外30%的数据 n<=100，m=n-1，k<=50;
对于100%的数据 n<=1000，m<=2500，k<=100;
思路：
看到互相到达点权位0自然想到缩点
缩完点后对于每组询问跑djstl即可
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define rii register int i #define rij register int j #define inf 19260817 using namespace std; int n,m,k,low[1005],dfn[1005],vis[1005]; int top,tot,color[1005],head[1005],sta[1005],bj[1005]; int cnt,bnt; struct ljb{ int nxt,to,val; }x[2505]; struct cb{ int from,to,val; }y[2505]; struct jd{ int bh,val; friend bool operator < (jd lk,jd kl) { return lk.val>kl.val; } }s[1005]; priority_queue<jd> q; void djstl(int wz) { for(rii=0;i<=n;i++) { s[i].bh=i; s[i].val=inf; } memset(bj,0,sizeof(bj)); s[wz].val=0; q.push(s[wz]); while(q.empty()!=true) { wz=q.top().bh; q.pop(); if(bj[wz]) { continue; } bj[wz]=true; for(rii=head[wz];i!=0;i=x[i].nxt) { if(bj[x[i].to]==1) { continue; } if(s[x[i].to].val>s[wz].val+x[i].val) { s[x[i].to].val=s[wz].val+x[i].val; q.push(s[x[i].to]); } } } } inline void add(int from,int to,int val) { bnt++; x[bnt].val=val; x[bnt].to=to; x[bnt].nxt=head[from]; head[from]=bnt; } void tarjan(int wz) { cnt++; low[wz]=cnt; dfn[wz]=cnt; top++; sta[top]=wz; vis[wz]=1; for(rii=head[wz];i!=0;i=x[i].nxt) { int ltt=x[i].to; if(dfn[ltt]==0) { tarjan(ltt); low[wz]=min(low[wz],low[ltt]); } else { if(vis[ltt]!=0) { low[wz]=min(low[wz],dfn[ltt]); } } } if(low[wz]==dfn[wz]) { tot++; while(sta[top+1]!=wz) { color[sta[top]]=tot; vis[sta[top]]=0; top--; } } } int main() { freopen("play.in","r",stdin); freopen("play.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(rii=1;i<=m;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); y[i].from=from; y[i].to=to; y[i].val=val; add(from,to,val); } for(rii=1;i<=n;i++) { if(dfn[i]==0) { tarjan(i); } } memset(x,0,sizeof(x)); memset(head,0,sizeof(head)); bnt=0; for(rii=1;i<=m;i++) { int from=y[i].from; int to=y[i].to; if(color[from]!=color[to]) { add(color[from],color[to],y[i].val); } } for(rii=1;i<=k;i++) { int from,to; scanf("%d%d",&from,&to); if(color[from]==color[to]) { puts("0"); continue; } djstl(color[from]); if(s[color[to]].val==inf) { puts("No"); } else { printf("%d ",s[color[to]].val); } } }