第十三届蓝桥杯C++B组国赛E题——出差 (AC)
CSDN话题挑战赛第2期
参赛话题：算法题解
1.出差
1.问题描述
A \mathrm{A} A 国有 N N N 个城市, 编号为 1 … N 1 \ldots N 1…N 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 N N N 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 N N N, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 M M M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 N \mathrm{N} N, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 N N N 。
2.输入格式
第 1 行: 两个正整数 N , M N, M N,M 表示 A 国的城市数量, M M M 表示末关闭的路线数量
第 2 行: N N N 个正整数, 第 i i i 个整数 C i C_{i} Ci表示到达编号为 i {i} i 的城市后需要隔离的时间
第 3 … M + 2 3 \ldots M+2 3…M+2 行: 每行 3 个正整数, u , v , c u, v, c u,v,c 表示有一条城市 u u u 到城市 v v v 的 双向路线仍然开通着, 通过该路线的时间为 c c c
3.输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 N N N 的最短时间（到达城市 N N N, 不需要计算城市 N N N 的隔离时间）
4.样例输入
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5
5.样例输出
13
6.样例说明
7.数据范围
对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000 , 1 ≤ C i ≤ 200 , 1 ≤ u , v ≤ N , 1 ≤ c ≤ 1000 1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1≤u,v≤ N, 1 \leq c \leq 1000 1≤N≤1000,1≤M≤10000,1≤Ci≤200,1≤u,v≤N,1≤c≤1000
8.原题链接
出差
2.解题思路
题意很明显考察的是一个最短路径问题，虽然题目说了给定的是双向边，但是假设g[i]的含义是到达i城市需要隔离的时间。假设有城市A和城市B,且两城市存在一条权值为w的双向边，当我们从A去到B所需要花费的时间应该是w+g[B],当我们从B去到A所花的时间应该是w+g[A]。所以虽然题意是双向边，但是方向不同的情况下，权值并不一定相同，所以我们应该看成两条边。
也就是说,存在邻接矩阵gra[][]，gra[i][j]表示从i到j的所需要的时间，g[i][j]和g[j][i]并不一定是相等的。所以我们在建图时应该分清楚，需要注意的是终点n的隔离时间我们是不考虑的，所以我们要把它置为0。然后建图完毕后直接跑一遍最短路算法即可，由于
n
n
n的最大只有1000,所以使用朴素dijkstra算法也是能过的。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
3.模板代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
//邻接矩阵
int gra[N][N];
int dist[N];
int g[N];
bool st[N];
int n,m;
//朴素版dijkstra
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + gra[t][j]);
st[t] = true;
}
return dist[n];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>g[i];
g[n]=0;
memset(gra, 0x3f, sizeof gra);
for(int i=1;i<=m;++i){
int u,v,c;
cin>>u>>v>>c;
gra[u][v]=g[v]+c;
gra[v][u]=g[u]+c;
}
cout<<dijkstra()<<endl;
return 0;
}