简单题目。。
/* 简单的bfs */ #include<algorithm> #include<iostream> #include<string.h> #include<stdlib.h> #include<stdio.h> #include<math.h> #include<queue> #include<stack> #include<map> #include<set> using namespace std; typedef long long int64; //typedef __int64 int64; typedef pair<int64,int64> PII; #define MP(a,b) make_pair((a),(b)) const int inf = 0x3f3f3f3f; const double pi=acos(-1.0); const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; const double eps = 1e-8; const int maxm = 1000005; const int maxn = 1005; struct Edge{ int u,v,next,val; }edge[ maxm*2 ]; int cnt ,head[ maxn ]; bool vis[ maxn ]; int dis1[ maxn ],dis2[ maxn ],girl[ maxn ]; //int dp[ maxn ]; queue<int>q; //int pre[ maxn ]; void init(){ cnt = 0; memset( head,-1,sizeof( head ) ); } void addedge( int a,int b,int c ){ edge[ cnt ].u = a; edge[ cnt ].v = b; edge[ cnt ].val = c; edge[ cnt ].next = head[ a ]; head[ a ] = cnt ++; } int spfa( int n ){ while( !q.empty() ) q.pop(); //memset( pre,-1,sizeof( pre ) ); memset( vis,false,sizeof( vis ) ); memset( dis1,0x3f,sizeof( dis1 ) ); memset( dis2,0x3f,sizeof( dis2 ) ); vis[ 1 ] = true; q.push( 1 ); dis1[ 1 ] = 0; dis2[ 1 ] = girl[ 1 ]; //for( int i=head[1];i!=-1;i=edge[i].next ){ // pre[ edge[i].v ] = 1; //} while( !q.empty() ){ int cur = q.front(); q.pop(); vis[ cur ] = false; for( int i=head[cur];i!=-1;i=edge[i].next ){ int nxt = edge[ i ].v; if( dis1[nxt]>dis1[cur]+edge[i].val ){ dis1[nxt] = dis1[cur]+edge[i].val; //pre[ nxt ] = cur; dis2[nxt] = dis2[cur]+girl[edge[i].v]; if( !vis[nxt] ){ vis[nxt] = true; q.push( nxt ); } } else if( dis1[nxt]==dis1[cur]+edge[i].val ){ if( dis2[nxt]<dis2[cur]+girl[edge[i].v] ){ //pre[ nxt ] = cur; dis2[nxt]=dis2[cur]+girl[edge[i].v]; if( !vis[nxt] ){ vis[nxt] = true; q.push( nxt ); } } } } } //printf("dis1[ %d ] = %d\n",n,dis1[n]); if( dis1[n]>=0x3f3f3f3f ) return -1; else return dis2[ n ]; /* int ans = 0; int cur = n; while( 1 ){ ans += girl[ cur ]; cur = pre[ cur ]; if( cur==-1 ){ break; } } return ans; */ } int main(){ int n; while( scanf("%d",&n)==1 ){ int m; scanf("%d",&m); for( int i=1;i<=n;i++ ) scanf("%d",&girl[i]); int a,b,c; init(); while( m-- ){ scanf("%d%d%d",&a,&b,&c); //if( a==b ) continue; addedge( a,b,c ); addedge( b,a,c ); } printf("%d\n",spfa( n ) ); } return 0; }