第十三届蓝桥杯C++B组国赛E题——出差 (AC)

叁歲伎倆 2023-09-28 23:11 31阅读 0赞

[CSDN话题挑战赛第2期][CSDN_2]  
参赛话题：

#### 目录 ####

*  1.出差
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.样例说明
     *  7.数据范围
     *  8.原题链接
 *  2.解题思路
 *  3.模板代码

## 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.样例输出 ###

### 6.样例说明 ###

![在这里插入图片描述][3f59a8713447422f84c2d9504f399782.png]

### 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.原题链接 ###

[出差][Link 1]

## 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;
    }

[CSDN_2]: https://marketing.csdn.net/p/7b6697fd9dd3795a268d1a6f2fe75012
[3f59a8713447422f84c2d9504f399782.png]: https://img-blog.csdnimg.cn/3f59a8713447422f84c2d9504f399782.png
[Link 1]: https://www.lanqiao.cn/problems/2194/learning/