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

## 有没有哪位大神愿意看一下这段代码哪里有问题啊？wa到吐……不胜感激

Posted by littlenum at 2012-09-01 21:02:36 on Problem 3013
```#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 10000000000000
#define maxn 50005
struct EDGE{

int end;
int weight;
int next;
}edge[maxn*2];
int price[maxn];
long long dis[maxn];
bool vis[maxn];

int e,v;

void spfa(){
queue <int> q;
memset(vis,0,sizeof(vis));
for(int i=0 ; i<=e ; i++)
dis[i]=inf;
dis[1]=0;
vis[1]=true;
q.push(1);
while(!q.empty()){

int now=q.front();
q.pop();
vis[now]=true;
for(int i=head[now] ; i ; i=edge[i].next)
if(dis[edge[i].end] > dis[now] + edge[i].weight){
dis[edge[i].end] = dis[now] + edge[i].weight;
if(!vis[edge[i].end]){
vis[edge[i].end]=true;
q.push(edge[i].end);
}
}
}
}

int main(){
int test;
scanf("%d",&test);
while(test--){

int a,b,w;
scanf("%d%d",&e,&v);
memset(price,0,sizeof(price));
for(int i=1 ; i<=e ; i++)
scanf("%d",&price[i]);
int cnt=1;
for(int i=0 ; i<v ; i++){

scanf("%d%d%d",&a,&b,&w);
edge[cnt].end=b;
edge[cnt].weight=w;
edge[cnt].end=a;
edge[cnt].weight=w;
}
if(e==0||e==1) {
printf("0\n");
continue;
}
spfa();
bool flag=true;
long long res=0;
for(int i=2 ; i<=e ; i++){

if(dis[i]==inf){

flag=false;
break;
}
res += price[i]*dis[i];
}

if(flag)
printf("%lld\n",res);
else

}
return 0;
}
```

Followed by: