AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
芝居気
,
2021-12-05 19:21:05
,
所有人可见
,
阅读 117
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;
int n, m;
unordered_map<int, unordered_map<int,int>>mp;
const int N = 505;
int f[N];
int ans[N];
bool st[N];//已确认最短路的点
void add(int a, int b, int len)
{
if(!mp[a][b])
mp[a][b] = len;
mp[a][b] = min(mp[a][b],len);
}
int dijkstra()
{
memset(ans, 0x3f, sizeof ans);
ans[1] = 0;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (st[j] == 0 && (t == -1 || ans[t] > ans[j]))
t = j; //再没确定最短路的点中 找一个最短路径的点。该点可以被确定。
} //所有已确定的点更新了所有未确定点,那么未确定点的最小值已经无法通过剩下的点变的更小(即未确定的点中更大的值);所有该点自然已经确定
st[t] = 1;
//要维护上一句话的正确性,每一次确定一个点都要使用该点更新所有点的最小值。(其实是未确定的点,已确定不会别更新,但同样遍历。)
//cout<<"t::" << t<<"min: "<<ans[t]<<endl;;
for (int j = 1; j <= n; j++)
{
if(mp[t].find(j)!=mp[t].end())//如果通过已确定的t可以达到t,则更新最短路。
ans[j] = min(ans[j], ans[t] + mp[t][j]);
}
}
if (ans[n] < 0x3f3f3f3f) return ans[n];
else return -1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
cout<<dijkstra();
}