Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

用了tarjan和spfa，WA，求大神查错

Posted by bowending at 2017-09-07 20:45:52 on Problem 3114
```#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int n,m,k,tot=0,color=0;
int dfn[510],low[510],colour[510],map[510][510],neww[510][510];
vector<int>g[510];
stack<int>s;
int que[510],vist[510],dist[510];
int min(int x,int y)
{
if(x>y) return y;
return x;
}
void dfs(int x)
{
int u,v,i;
tot++;
dfn[x]=tot;
low[x]=tot;
s.push(x);
for(i=0;i<g[x].size();i++)
{
u=g[x][i];
if(dfn[u]==0)
{
dfs(u);
low[x]=min(low[x],low[u]);
}
else if(colour[u]==0)
low[x]=min(low[x],dfn[u]);
}
if(dfn[x]==low[x]) {
color++;
while(true)
{
v=s.top();
s.pop();
colour[v]=color;
if(x==v) break;
}
}
}
int  spfa(int x,int goal)
{
int u,v,i;
u=que[1]=colour[x];
vist[que[1]]=1;
goal=colour[goal];
dist[u]=0;
{
for(i=1;i<=color;i++)
if(neww[u][i]!=0&&dist[i]>dist[u]+neww[u][i])
{
dist[i]=dist[u]+neww[u][i];
if(vist[i]==0)
{
tail++;
que[tail]=i;
vist[i]=1;
}
}
vist[u]=0;
}
return dist[goal];
}
void initt()
{
memset(vist,0,sizeof(vist));
memset(que,0,sizeof(que));
memset(dist,127,sizeof(dist));
}
void init()
{
int i;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(colour,0,sizeof(colour));
for(i=0;i<n;i++)
g[i].clear();
tot=0; color=0;
}
int main()
{
freopen("poj3114.in","r",stdin);
freopen("poj3114.out","w",stdout);

int i,j,x,y,h,u;
while(true)
{
scanf("%d",&n);
if(n==0) break;
scanf("%d",&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&h);
g[x].push_back(y);
map[x][y]=h;
}
for(i=1;i<=n;i++)
if(dfn[i]==0)
dfs(i);
for(i=1;i<=n;i++)
for(j=0;j<g[i].size();j++)
{
u=g[i][j];
if(colour[i]!=colour[u]){
if(neww[colour[i]][colour[u]]==0)
neww[colour[i]][colour[u]]=map[i][u];
else neww[colour[i]][colour[u]]=min(neww[colour[i]][colour[u]],map[i][u]);
}
}
int ans=0;
scanf("%d",&k);
while(k>0)
{
initt();
k--;
scanf("%d%d",&x,&y);
ans=spfa(x,y);
if(ans==2139062143) printf("Nao e possivel entregar a carta\n");
else printf("%d\n",ans);
}
printf("\n");
}
return 0;
}```

Followed by: