[牛客]公交线路(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];
}