赛艇表演(造超级原点+最短路)-布布扣-bubuko.com

题目描述

小明去某个地区观看赛艇比赛，这个地区共有n个城市和m条道路，每个城市都有赛艇比赛，在第i个城市观看赛艇表演的价钱为ai，去其他城市观看也需要支付赛艇表演的价格。任意两个城市之间通过一条公路连接，并且道路是双向通行的，观看赛艇比赛时经过的每一条道路都要支付一定的过路费，观看完比赛返回家时经过的每一条道路也要支付过路费。
对于每个城市u，你需要为小明确定一个城市v，使得从u出发，前往v看赛艇表演，再从v回到u，u可以等于v，要求花费的总金额尽量的少。请根据题目给出的数据输出总金额。

输入

第一行两个正整数n和m。
接下来m行，每行三个正整数u，v，w，表示有一条双向道路连接u和v，且每经过一次的过路费是w。接下来一行n个数，第i个数表示在第i个城市观看赛艇表演的价钱。

输出

输出一行n个数，第i个数表示从第i个城市出发至少要花多少钱

样例输入 Copy

样例输出 Copy

6 14 1 25

提示

对于前30%的数据，n<=10，m<=20。
对于前50%的数据，n<=100，m<=500。
对于前70%的数据，n<=1500，m<=2000。
对于前85%的数据，图的结构以某种方式随机生成。
对于100%的数据，n<=2e5，m<=2e5，过路费和门票钱都在[1,1e12]内。

首先，如果暴力找每一个点的最短路一定T

所以，考虑将结点权值加在边上，先造一个超级原点，使每个点到原点的都有一条双向边，且边权是结点权值，其次每条边的边权是来回两次，边权是2*w；

如图建图；

代码如下

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e5+50;
 4 typedef long long ll;
 5 struct ss
 6 {
 7     int u,v,next;
 8     ll w;
 9 }edg[N*5];
10 int sumedg,head[N];
11 void addedg(int u,int v,ll w)
12 {
13     edg[sumedg]=(ss){u,v,head[u],w};
14     head[u]=sumedg++;
15 }
16 ll n,m,value[N];
17 ll dis[N];
18 bool vis[N];
19 void spfa()
20 {
21     queue<int>q;
22     memset(vis,0,sizeof(vis));
23     for(int i=0;i<n+10;i++) dis[i]=LONG_LONG_MAX;
24     q.push(0);
25     vis[0]=1;
26     dis[0]=0;
27     while(!q.empty())
28     {
29         int now=q.front();q.pop();vis[now]=0;
30         for(int i=head[now];i!=-1;i=edg[i].next)
31         {
32             int v=edg[i].v;
33             long long w=edg[i].w;
34   
35             if(dis[v]>dis[now]+w)
36             {
37                 dis[v]=dis[now]+w;
38                 if(!vis[v])
39                 {
40                     q.push(v);
41                     vis[v]=1;
42                 }
43             }
44         }
45     }
46   
47 }
48 int main()
49 {
50     scanf("%lld%lld",&n,&m);
51     memset(dis,0,sizeof(dis));
52     for(ll i=0;i<n+10;i++) head[i]=-1;
53     for(ll i=0;i<m;i++)
54     {
55         int u,v;ll w;
56         scanf("%d%d%lld",&u,&v,&w);
57         addedg(u,v,w*2);
58         addedg(v,u,w*2);
59     }
60     for(ll i=1;i<=n;i++)
61     {
62         scanf("%lld",&value[i]);
63         addedg(0,i,value[i]);
64         addedg(i,0,value[i]);
65     }
66     spfa();
67     for(ll i=1;i<=n;i++)
68     {
69          printf("%lld%c",dis[i],i==n?‘\n‘:‘ ‘);
70     }
71     return 0;
72 }