没想到手感还在~ 不需要重新建图，只要根据条件改改权值即可。还跑k次SPFA~
#include<cstdio>#include<iostream>#include<stack>#include<queue>#include<algorithm>using namespace std; const int MAXN=600; const int MAXE=500*500*2+100;int e[MAXE][3];int head[MAXN];int nume;int n,m,k;void adde(int i,int j,int w){e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;e[nume++][2]=w;}int dfn[MAXN];int low[MAXN];int ins[MAXN];stack<int>sta;int times;int scc[MAXN];int block;int vis[MAXN];void tarjan(int u){dfn[u]=low[u]=times++;ins[u]=1;sta.push(u);for(int j=head[u];j!=-1;j=e[j][1]){int v=e[j][0];if(!vis[v]){vis[v]=1;tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int cur;block++;do{cur=sta.top();sta.pop();ins[cur]=0;scc[cur]=block;}while(cur!=u);}}void rebuild(){for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=e[j][1]){int to=e[j][0];if(scc[i]==scc[to]){e[j][2]=0;}}}int d[MAXN];int inq[MAXN];const int inf=0x3f3f3f3f;int spfa(int s,int t){for(int i=1;i<=n;i++){d[i]=inf;inq[i]=0;}d[s]=0;queue<int>q;q.push(s);inq[s]=1;while(!q.empty()){int cur=q.front();q.pop();inq[cur]=0;for(int j=head[cur];j!=-1;j=e[j][1]){int to=e[j][0];if(d[to]>d[cur]+e[j][2]){d[to]=d[cur]+e[j][2];if(!inq[to]){inq[to]=1;q.push(to);}}}} return d[t];}void init(){for(int i=0;i<MAXN-2;i++){vis[i]=dfn[i]=low[i]=ins[i]=0;head[i]=-1;}block=nume=times=0;}int main(){while(~scanf("%d%d",&n,&m)&&n){init();for(int i=0;i<m;i++){int aa,bb,cc;scanf("%d%d%d",&aa,&bb,&cc);adde(aa,bb,cc);}scanf("%d",&k);for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=1;tarjan(i);}}rebuild();int ss,tt;for(int i=0;i<k;i++){scanf("%d%d",&ss,&tt);int ans=spfa(ss,tt);if(ans!=inf)printf("%d\n",ans);elseprintf("Nao e possivel entregar a carta\n");}printf("\n");}return 0;}
，再发展下来才有了：大霞美的花卉基地和清源山的花博园。
