题目就是一道最短路的变形 数据比较大 所以使用邻接表以及队列来完成
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<vector> #include<map> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define N 100006 int k,dis[N],aa[N],w[N]; struct node { int e,f,g,v; }a[N<<1]; void add(int e,int f,int g) { a[k].f=f; a[k].g=g; a[k].v=aa[e]; aa[e]=k++; } queue<int>Q; void q() { while(Q.size()) { int e=Q.front();Q.pop(); w[e]=0; for(int i=aa[e];i!=-1;i=a[i].v) { int f=a[i].f; int g=a[i].g; if(dis[g]>dis[e]+dis[f]) { dis[g]=dis[e]+dis[f]; if(!w[g]) { w[g]=1; Q.push(g); } } } } } int main() { int T,n,m,e,f,g; scanf("%d",&T); while(T--) { k=0; memset(w,0,sizeof(w)); memset(aa,-1,sizeof(aa)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&dis[i]); for(int i=0;i<m;i++) { scanf("%d%d%d",&e,&f,&g); add(e,f,g); add(f,e,g); if(!w[e]) Q.push(e); w[e]=1; } q(); for(int i=1;i<=n;i++) printf("%d%c",dis[i],i==n?' ':' '); } return 0; }