hdu 4171 最短路

#include<stdio.h>

#include<string.h>

#include<queue>

#include<iostream>

using namespace std;

#define inf 1000000000

#define N 110000

struct node {

int u,v,w,next;

}bian[N*2];

int head[N],yong,mindistance[N],n,visit[N],countt[N];

void addedge(int u,int v,int w) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

void min_spfa(int cur) {

int i;

for(i=0;i<=n;i++) {

mindistance[i]=inf;

visit[i]=0;

countt[i]=0;//原来在c++中的某些关键字不能乱用比如说count之类

}

visit[cur]=1;

queue<int>q;

q.push(cur);

mindistance[cur]=0;

while(!q.empty()) {

cur=q.front();

q.pop();

for(i=head[cur];i!=-1;i=bian[i].next) {

int v=bian[i].v;

if(mindistance[v]>mindistance[cur]+bian[i].w) {

mindistance[v]=mindistance[cur]+bian[i].w;

if(!visit[v]) {

if(++countt[v]>n)

return ;

visit[v]=1;

q.push(v);

}

}

}

visit[cur]=0;

}

return ;

}

int main() {

int i,a,b,c,dis[N],sum,minsum;

while(scanf("%d",&n)!=EOF) {

yong=0;

memset(head,-1,sizeof(head));

for(i=0;i<=n;i++)

scanf("%d",&dis[i]);

sum=0;

for(i=0;i<n;i++) {

scanf("%d%d%d",&a,&b,&c);

addedge(a,b,c);

addedge(b,a,c);

sum=sum+c*2;

}

min_spfa(0);

minsum=sum+dis[0];

for(i=1;i<=n;i++) {

if(minsum>sum-mindistance[i]+dis[i])

minsum=sum-mindistance[i]+dis[i];

}

printf("%d\n",minsum);

}

return 0;

}

巴特西

hdu 4171 最短路

最新文章

热门文章