公交线路

公交线路

解题思路
Dijkstra算法，基于贪心思想，适用于边的权值非负

算法流程：
1.初始化dis[s]=0,其他节点值为无穷大
2.找出一个未标记的，dis[x]最小的节点x,标记x
3.更新x的所有出边
4.重复2~3，直到所有点被标记

邻接矩阵写法

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
int a[N][N];
int dis[N];
int vis[N];

int n,m,s,t;
int x,y,v;

void dij(int s)
{
    dis[s]=0;
    for(int i=1;i<n;i++)
    {
        int x=0;
        int y;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&(x==0||dis[j]<dis[x]))
            {
                x=j;
            }
        }
        vis[x]=1;
        for(int j=1;j<=n;j++)
        {
            dis[j]=min(dis[j],dis[x]+a[x][j]);
        }
    }
}

int main()
{
    memset(a,0x3f,sizeof(a));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>v;
        a[x][y]=min(v,a[x][y]);
        a[y][x]=min(v,a[y][x]);
    }
    dij(s);
    if(dis[t]>=0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dis[t]<<endl;

    return 0;
}

链式前向星写法

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int N=1010;
const int M=20010;
int head[N],e[M],ne[M],w[M];
int dis[N];
bool vis[N];
int tot;
int n,m,s,t;
int x,y,v;

void add(int x,int y,int z)
{
    e[++tot]=y;
    w[tot]=z;
    ne[tot]=head[x];
    head[x]=tot;
}

void dij(int s)
{
    priority_queue<pii> p;
    dis[s]=0;
    p.push({0,s});
    while(p.size())
    {
        int x=p.top().second;
        p.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=ne[i])
        {
            int y=e[i];
            int z=w[i];
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                p.push({-dis[y],y});
            }
        }
    }
}

int main()
{
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>v;
        add(x,y,v);
        add(y,x,v);
    }
    dij(s);
    if(dis[t]>=0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dis[t]<<endl;

    return 0;
}