没想到手感还在~ 不须要又一次建图。仅仅要依据条件改改权值就可以。
还跑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);
else
printf("Nao e possivel entregar a carta\n");
}
printf("\n");
}
return 0;
}