模板:(单源最短路径+链式前向星)

洛谷中的一道模板题

原题链接:https://www.luogu.com.cn/problem/P3371

以前学链式前向星的时候没怎么认真学,觉得没啥用,用邻接矩阵不香吗

刚刚做了洛谷这道dijsktra的板子题,1e4个点,当时没在意,直接开了[10000][10000],结果有三个测试点内存超限了

没办法,必须换个存储结构了,但写邻接表是不可能的,太麻烦了,于是

链式前向星真香啊

 

链式前向星的存储结构:

struct node
{
    int to;//终点
    int w; //权值
    int next;//相同开始点的下一条边的编号;(用来通过下一条边寻找这一条边;)
}q;
int head[MaxSize];//head[i]表示以 i 为q起点的边的位置

当我们存图的时候

for(int i = 1; i <= m; i++)//m条边
{
    int t1, t2, t3;
    cin >> t1  >> t2 >> t3;//表示t1到t2的距离为t3
    q[i].to = t2;//终点
    q[i].w  = t3;//权值
    q[i].next = head[t1];//以t1为起点的下一点的编号,如果值为-1就代表没有下一点了;
    head[t1] = i;//不断改变head的值
}

是一个从后往前找的过程

比如,输入这样一组图的数据

1 2 3

1 4 1

3 2 2

3 5 1

1 3 2

4 2 1

2 5 5

那么在链式前向星中存储的是:

起点为1:
1 2 3
1 4 1
1 3 2
 
起点为2:
2 5 5
 
起点为3:
3 2 2
3 5 1
 
起点为4:
4 2 1
 
起点为5:
无  

大致就是这样

至于dijsktra算法不多做解释了(ps:应该学一下SPFA了。。。)

原题代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct qq
{
    int to;
    int w;
    int next;
}q[500010];
int head[10010],dis[10010],book[10010],inf=99999999;
void init()
{
    for(int i=0;i<10010;i++)
    {head[i]=-1;}
}
int main()
{
    init();
    int n,m,s,t1,t2,t3;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        q[i].to=t2;
        q[i].w=t3;
        q[i].next=head[t1];
        head[t1]=i;
    }
    for(int i=1;i<=n;i++)
    {dis[i]=inf;}
    dis[s]=0;
    for(int i=head[s];i!=-1;i=q[i].next)
    {
        dis[q[i].to]=min(dis[q[i].to],q[i].w);
    }
    book[s]=1;
    int u;
    for(int i=1;i<=n-1;i++)
    {
        int minn=inf;
        for(int j=1;j<=n;j++)
        {
            if(dis[j]<minn&&book[j]==0)
            {
                minn=dis[j];
                u=j;
            }
        }
        book[u]=1;
        for(int j=head[u];j!=-1;j=q[j].next)
        {
            if(dis[q[j].to]>dis[u]+q[j].w)
            {
                dis[q[j].to]=dis[u]+q[j].w;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==inf)
        {cout<<"2147483647 ";}
        else
        {cout<<dis[i]<<" ";}
    }
    cout<<endl;
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注