[牛客]公交线路(dijkstra+链式前向星)

登录—专业IT笔试面试备考平台_牛客网

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e6+5,M=1e8+5;
int cnt=0,head[N];
int n,m,s,t;
struct node
{int v,w,next;
}edge[M];
void addedge(int u,int v,int w)
{cnt++;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt;
}
bool vis[N];
int dis[N];
void dijkstra()
{for(int i=1;i<=n;i++)dis[i]=INT_MAX;int curr=s;dis[s]=0;int minn;while(!vis[curr]){vis[curr]=true;for(int i=head[curr];i>0;i=edge[i].next){if(!vis[edge[i].v] && dis[edge[i].v]>dis[curr]+edge[i].w){dis[edge[i].v]=dis[curr]+edge[i].w;}}minn=INT_MAX;for(int i=1;i<=n;i++){if(!vis[i] && minn>dis[i]){minn=dis[i];curr=i;}}}
}
int main()
{cin>>n>>m>>s>>t;for(int i=0;i<m;i++){int a,b,v;cin>>a>>b>>v;addedge(a,b,v),addedge(b,a,v);}dijkstra();if(!vis[t])cout<<-1;else cout<<dis[t];
}