CSU1321+SPFA

简单题目。。

/*
简单的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;
}