4 2 1 2 4 2 3 7 6 20 1 25
6 14 1 25 
3 3 1 2 1 2 3 1 1 3 1 30 10 20
12 10 12

思路:

建立虚点把点券转化成边权

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define int long long #define maxn 850500 using namespace std ; int read() { int x = 0 , f = 1 ; char s = getchar() ; while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;} while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;} return x*f ; } int n , m ; struct dy{ int x , y ,z ,next ; }a[maxn] ; int head[maxn] , vis[maxn] , dis[maxn] , t ; void add(int x ,int y ,int z) { a[++t].x = x ; a[t].y = y ; a[t].z = z ; a[t].next = head[x] ; head[x] = t ; } typedef pair<int,int>pa ; priority_queue<pa,vector<pa>,greater<pa> >q ; void dij(int s) { memset(dis,0x3f,sizeof(dis)) ; memset(vis,0,sizeof(vis)) ; dis[s] = 0 , vis[s] = 0 ; q.push(make_pair(dis[s],s)) ; while(!q.empty()) { int u = q.top().second ; q.pop() ; if(vis[u]) continue ; vis[u] = 1 ; for(int i = head[u] ; i ; i = a[i].next ) { int v = a[i].y ; if(dis[v] > dis[u] + a[i].z ) { dis[v] = dis[u] + a[i].z ; q.push(make_pair(dis[v],v)) ; } } } } signed main () { n = read() , m = read() ; while(m --) { int x = read() , y = read() , z = read() ; add(x,y,z*2) ; add(y,x,z*2) ; } for(int i = 1 ; i <= n ; i ++) { int x = read() ; add(0,i,x) ; add(i,0,x) ; }dij(0) ; for(int i = 1 ; i <= n ; i ++) { printf("%I64d ",dis[i]) ; } return 0 ; }