AcWing 851. spfa求最短路
原题链接
简单
作者:
HUE菜鸡联盟
,
2021-12-06 20:11:01
,
所有人可见
,
阅读 126
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<string.h>
#define for0(x,n) for(int x=0;x<n;x++)
#define for1(x,n) for(int x=1;x<=n;x++)
using namespace std;
typedef long long ll;//long long
typedef pair<double,double>PDD;
typedef pair<int,int> PII;
const int tt=1e5+10,mod=1e9+7,INF=0x7f7f7f7f7f7f7f7f;
int n,m;
int ans=0;
int vis[tt];
int d[tt];
vector<PII>G[tt];
int spfa()
{
queue<PII>q;
memset(d,INF,sizeof(d));
d[1]=0;
q.push({1,0});
vis[1]=1;
while(!q.empty())
{
PII now=q.front();
q.pop();
int to=now.first;
vis[to]=0;
for0(i,G[to].size())
{
int j=G[to][i].first;
if(d[j]>d[to]+G[to][i].second)
{
d[j]=d[to]+G[to][i].second;
if(!vis[j])
{
vis[j]=1;
q.push(PII(j,d[j]));
}
}
}
}
return d[n];
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
G[x].push_back(PII(y,z));
}
int ans=spfa();
ans==INF?cout<<"impossible":cout<<ans;
}