Skip to content

Instantly share code, notes, and snippets.

@kuoe0
Last active December 20, 2015 15:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kuoe0/6154538 to your computer and use it in GitHub Desktop.
Save kuoe0/6154538 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 610
struct EDGE {
int a, b, c;
};
EDGE edge[ 10010 ];
vector< int > vertex[ MAXN ];
int cost[ MAXN ][ MAXN ];
int camp[ MAXN ], dist[ MAXN ];
bool visit[ MAXN ];
int n, e;
int dijkstra( int st, int ed ) {
typedef pair< int, int > NODE;
priority_queue< NODE, vector< NODE >, greater< NODE > > PQ;
memset( visit, 0, sizeof( visit ) );
memset( dist, 63, sizeof( dist ) );
dist[ st ] = 0;
PQ.push( pair< int, int >( dist[ st ], st ) );
while ( !PQ.empty() ) {
int now = PQ.top().second;
PQ.pop();
visit[ now ] = 1;
for ( int i = 0; i < vertex[ now ].size(); ++i ) {
int next = vertex[ now ][ i ];
if ( !visit[ next ] && dist[ now ] + cost[ now ][ next ] < dist[ next ] ) {
dist[ next ] = dist[ now ] + cost[ now ][ next ];
PQ.push( pair< int, int >( dist[ next ], next ) );
}
}
}
return dist[ ed ] == dist[ 0 ] ? -1 : dist[ ed ];
}
int main() {
while ( ~scanf( "%d", &n ) && n ) {
scanf( "%d", &e );
for ( int i = 1; i <= n; ++i )
vertex[ i ].clear();
int a, b, c;
for ( int i = 0; i < e; ++i )
scanf( "%d %d %d", &edge[ i ].a, &edge[ i ].b, &edge[ i ].c );
for ( int i = 1; i <= n; ++i ) {
scanf( "%d", &c );
camp[ i ] = c;
}
for ( int i = 0; i < e; ++i ) {
if ( camp[ edge[ i ].a ] == camp[ edge[ i ].b ] ) {
cost[ edge[ i ].a ][ edge[ i ].b ] = cost[ edge[ i ].b ][ edge[ i ].a ] = edge[ i ].c;
vertex[ edge[ i ].a ].push_back( edge[ i ].b ), vertex[ edge[ i ].b ].push_back( edge[ i ].a );
}
else if ( camp[ edge[ i ].a ] == 1 )
cost[ edge[ i ].a ][ edge[ i ].b ] = edge[ i ].c, vertex[ edge[ i ].a ].push_back( edge[ i ].b );
else
cost[ edge[ i ].b ][ edge[ i ].a ] = edge[ i ].c, vertex[ edge[ i ].b ].push_back( edge[ i ].a );
}
printf( "%d\n", dijkstra( 1, 2 ) );
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment