小木乃伊到我家（牛客竞赛）（最短路模板题）

木乃伊到我家（牛客竞赛）（最短路模板题）"/>

小木乃伊到我家（牛客竞赛）（最短路模板题）

题源

dijkstra做法

注意：

1.距离要初始化为inf

2.边的存储要弄清存储的方式，以及各自代表的含义；
比如说pair存储，first代表边的指向的点，second代表边的权值，而数组的第一维代表边的起点。

3.优先队列存储的信息要清楚它的作用：

存储距离：目的是对距离进行排序，每次取出距离最小的节点，功能只是对队列的节点进行排序。
存储节点：目的是为了取出最短距离的节点时，能够获得节点的编号。
所以在优先队列里面，存储距离加了个负号，因为优先队列优先对pair的第一个元素进行降序排序，所以为了取出最小距离的节点，需要加个负号。
并且加了负号的距离并没有对我们产生影响，我们需要的只是节点的编号。

#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5+5;
const int inf = 0x3f3f3f3f;
vector<pii>e[N];
ll dis[N];
void dijkstra()
{int x = 1;priority_queue<pii>q;dis[x] = 0;q.push({-dis[x],x});while(!q.empty()){pii t = q.top();q.pop();for(int i=0;i<e[t.se].size();i++){int too = e[t.se][i].fi;if(dis[too] > dis[t.se] + e[t.se][i].se){dis[too] = dis[t.se] + e[t.se][i].se;q.push({-dis[too],too});}}}
}
int main()
{for(int i=1;i<=N;i++) dis[i] = inf;int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;e[a].push_back({b,c});e[b].push_back({a,c});}dijkstra();if(dis[n]!=inf) cout<<dis[n]<<'\n';else cout<<"qwb baka\n";return 0;
}

SPFA做法

#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5+5;
const int inf = 0x3f3f3f3f;
vector<pii>e[N];
ll dis[N];
bool vis[N];
void spfa()
{int s = 1;vis[s] = 1;dis[s] = 0;queue<int>q;q.push(s);while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i=0;i<e[u].size();i++){int v = e[u][i].fi;if(dis[v] > dis[u]+e[u][i].se){dis[v] = dis[u] + e[u][i].se;if(!vis[v]){vis[v] = true;q.push(v);}}}}
}int main()
{for(int i=1;i<=N;i++) dis[i] = inf;int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;e[a].push_back({b,c});e[b].push_back({a,c});}spfa();if(dis[n]!=inf) cout<<dis[n]<<'\n';else cout<<"qwb baka\n";return 0;
}