47. 参加科学大会（第六期模拟笔试）（最短路）

链接：卡码网KamaCoder

题目：

样例：

4 5
0 2 7 3
1 2
1 3
2 3
2 4
3 4

思路：

        由题意，很明显这是一道最短路径问题，但是不同的是，这里没有给出边的长度，而是以结点权值的形式，变相的作为边长，这一我们应该注意的是，这里的意思为

从 a 点到 b点所花时间为   b  即  g[a][b] = b  ，从 b 点到 a 点所花时间为  a  即  g[b][a] = a 

所以我们根据题意，更改一下Dijkstra模板函数即可。

代码详解如下：

#include 
#include 
#include 
#include 
#include 
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define INF 0x3f3f3f3f
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1500 + 10;
int n,m;
 
int g[N][N];	// 所到结点所花的时间，即路径长度
 
umap<int,int>dist;	// 记录最短路径
 
umap<int,int>d;	// 记录结点权值，即所花时间
 
umap<int,bool>st;
 
inline int Dijkstra()
{
	// 初始化起点最短距离
	dist[1] = d[1];
	// 初始化 dist ，走一遍起点到每一个点的最短距离
	for(int i = 2;i <= n;++i)
	{
		dist[i] = g[1][i];
	}
	// 从起点走完一遍后，标记起点我们检查过了
	st[1] = true;
 
	// 这里 i = 2 是因为我们刚开始已经走过一遍起点了
	for(int i = 2;i < n;++i)
	{
		// t 探头探索哪一个点所花时间最少,即最短距离
		int t = -1;
		for(int j = 1;j <= n;++j)
		{
			if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
		}
		
		// 标记并走向该结点
		st[t] = true;
		
		// 更新所有结点最短距离
		for(int j = 1;j <= n;++j)
		{
			dist[j] = min(dist[j],dist[t] + g[t][j]);
		}
	}
	
	// 这里返回结果最后加上 d[1] 是因为可能起点也有需要花费的时间
	return dist[n] + d[1];
}
 
 
inline void solve()
{
	memset(g,INF,sizeof g);
	cin >> n >> m;	
	
	// 输入结点权值
	for(int i = 1;i <= n;++i)
	{
		cin >> d[i];
	}
	
	while(m--)
	{
		int a,b;
		cin >> a >> b;
		
		// 记录 a 点 到 b 点 的距离
		g[a][b] = d[b];
		
		// 记录 b 点 到 a 点 的距离
		g[b][a] = d[a];
	}
	
	int ans = Dijkstra();
	
	cout << ans << endl;
	
}
 
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：