[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
2
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 * 2 + 1001;
priority_queue
<pa
,vector
<pa
> ,greater
<pa
> > s
;
struct node
{
int next
,to
;
ll val
;
}edge
[MAXN
];
int head
[MAXN
] = {0} ,cnt
= 0;
void add
(int from
,int to
,ll value
) {
edge
[++ cnt
].next
= head
[from
];
head
[from
] = cnt
;
edge
[cnt
].to
= to
;
edge
[cnt
].val
= value
;
return ;
}
int n
,m
;
ll dis
[MAXN
];
int inq
[MAXN
];
void SPFA
(int st
) {
memset
(dis
,0x3f ,sizeof (dis
));
memset
(inq
,0 ,sizeof (inq
));
dis
[st
] = 0 ,inq
[st
] = 1;
s
.push(make_pair
(dis
[st
] ,st
));
while (!s
.empty()) {
int u
= s
.top().second
;
s
.pop();
inq
[u
] = 0;
for (int q
= head
[u
];q
;q
= edge
[q
].next
) {
int v
= edge
[q
].to
;
if (dis
[v
] > dis
[u
] + edge
[q
].val
) {
dis
[v
] = dis
[u
] + edge
[q
].val
;
if (! inq
[q
]) {
inq
[q
] = 1;
s
.push(make_pair
(dis
[v
] ,v
));
}
}
}
}
for (int q
= 1;q
<= n
;++ q
) {
printf
("%lld ",dis
[q
]);
}
printf
("\n");
return ;
}
int main
() {
scanf
("%d%d",&n
,&m
);
int from
,to
,value
;
for (int q
= 1;q
<= m
;++ q
) {
scanf
("%d%d%d",&from
,&to
,&value
);
add
(from
,to
,value
<< 1) ,add
(to
,from
,value
<< 1);
}
for (int q
= 1;q
<= n
;++ q
) {
scanf
("%d",&value
);
add
(n
+ 1 ,q
,value
) ,add
(q
,n
+ 1 ,value
);
}
SPFA
(n
+ 1);
return 0;
}
感想
仔细思考，巧用模型进行转化
——2020.10.6
