[COGS] 赛艇表演

题目描述

题目描述

小明去某个地区观看赛艇比赛，这个地区共有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个城市出发至少要花多少钱。

样例输入

4 2
1 2 4
2 3 7
6 20 1 25

样例输出

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]内。

解题过程

思路

这道题可以直接跑一边多源最短路，然后直接输出最小的花费即可

期望得分：70

由于每一个城市都有一个花费，我们可以考虑新建一个超级源点源，连接每一个城市，将超级源点到每个城市的路上花费设置成在城市看演出的花费，此时每两个城市之间的花费要乘 $2$ ，我们直接跑一边单源最短路即可

期望得分：100

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define pa pair <int ,long long >
using namespace std;
typedef long long ll;
const int MAXN = 4e5 *