题解 | #公交线路#

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;//n是点的数量m是边的数量从s到t的最短路就只需要把s到其他所有点的最短路求出来最后返回要求的那个点
int head[10005];//用于标记最后添加的某个点的第一条边用来遍历这点的所有边
struct tx//链式前向星
{
    int to,len,next;
}node[20005];//因为是无向边所以见两条边x->y,y->x注意djikstr可以求无向边只要没有负数边
int cnt;
void add(int x,int to,int len)//添加边
{
    //x是从那个点开始的边to是到那个边len是从x->to的边权
    node[++cnt].len=len;
    node[cnt].to=to;
    node[cnt].next=head[x];
    head[x]=cnt;
}
struct ty
{
    //x是点dis是距离
    int x,dis;
    bool operator<(const ty &that)const
    {
        //本来的优先队列是大的在前面所以这里手写比较函数让距离x小的点排在前面但是非线性容器比较函数要相反所以这里是大于号
        return dis>that.dis;
    }
};
//dis用来标记距离
int dis[1005];
//vis用来标记是否已经找到最短路
bool vis[1005];
int djikstra(int s,int t)//本质上就是正常的djiksta传入t是为了直接返回dis[t]实际上s的所有最短路都找到了
{
    //初始化两个数组因为这道题只有一组数据但是如果多组数据就需要这么做
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    //因为手写了比较函数所以这里面距离小的就会排在前面直接就可以找到距离最近的点
    priority_queue<ty>q;
    //把第一个点放进去因为是从s到其他的最短路s到s是0
    q.push({s,0});
    while(!q.empty())
    {
        //每次取出队头元素就是最近的点
        ty tmp=q.top();
        q.pop();
        //如果这个点已经找到最短路了就不用再找了
        if(vis[tmp.x])continue;
        //tmp.x是这个点存边的时候head数组标记的tmp.x是最后储存的以tmp.x为起点的下标
        //node[i]就是以这个tmp.x为起点的边next就是下一条边
        for(int i=head[tmp.x];i;i=node[i].next)
        {
            //to就是tmp.x为起点到的那个点
            int y=node[i].to;
            //同一个便可能遍历很多次所以去重
            if(vis[y])continue;
            //否则看能否更新最短路如果到y的距离大于到tmp.x的距离加上tmp.x到to的距离
            if(dis[y]>dis[tmp.x]+node[i].len)
            {
                dis[y]=dis[tmp.x]+node[i].len;
                //下次就用这个新的点去重新更新最短路
               q.push({y,dis[y]});
            }
        }
    }
    //全部更新完以后如果dis[t]等于0x3f3f3f3f说明他没办法更新返回-1否则正确更新返回dis[t]
    if(dis[t]==0x3f3f3f3f)
        return -1;
    return dis[t];
}
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int x,to,len;
        //从x->to的边长度为len
        cin>>x>>to>>len;
        //无向边建两条边
        add(x,to,len);
        add(to,x,len);
    }
    cout<<djikstra(s,t)<<endl;
}
*#include<bits/stdc++.h>

//朴素djikstra只能过案例当作品参考

using namespace std;

int g[100][100];

bool vis[100];

int dis[100];

int n,m,s,t;

void djikstra(int s,int n)

{

    dis[s]=0;

    for(int i=1;i<=n;i++)

    {

        int t=-1;

        for(int j=1;j<=n;j++)

        {

            if(!vis[j]&&(t==-1||dis[t]>dis[j]))

            {

                t=j;

            }

        }

        vis[t]=1;

        //现在t就是那个距离最近的点

        for(int j=1;j<=n;j++)

        {

            if(g[t][j]==-1)continue;//说明没有这条边

            if(dis[j]>dis[t]+g[t][j])

                dis[j]=dis[t]+g[t][j];

        }

    }

}

int main()

{

    cin>>n>>m>>s>>t;

    memset(dis,0x3f,sizeof(dis));

    memset(vis,0,sizeof(vis));

    memset(g,-1,sizeof(g));

    for(int i=1;i<=m;i++)

    {

        int x,t,w;

        cin>>x>>t>>w;

        g[x][t]=w;

        g[t][x]=w;

    }

    djikstra(s,n);

   if(dis[t]==0x3f3f3f3f)

       cout<<-1;

    else

        cout<<dis[t];

}*/