【弱化版】【P3371 【模板】单源最短路径（弱化版）】-C++

→原题传送门←

看到题目描述我就知道，这道题不能用SPFA[手动补滑稽]

那么我这道题目采用的是dijkstra算法不了解的去补一下知识哈.

dij的模板：

#include<bits/stdc++.h>

using namespace std;

int dst[5010];

int n,m;

bool s[5010];

int pre[5010];

struct node

{

    int v,w;

    node(){}

    node(int vv,int ww)

    {

        v=vv,w=ww;

    }

};

vector<node> g[5010];

void init()

{

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

    {

        dst[i]=0x7f7f7f7f;

    }

}

int main()

{

    init();

    int a,b,c;

    cin>>n>>m;

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

    {

        cin>>a>>b>>c;

        g[a].push_back(node(b,c));

        g[b].push_back(node(a,c));

    }

    s[1]=1;

    dst[1]=0;

    int lasti=1;

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

    {

        for(int j=0;j<g[lasti].size();j++)

        {

            int v=g[lasti][j].v,w=g[lasti][j].w;

            if(!s[v]&&w+dst[lasti]<dst[v])

            {

                pre[v]=lasti;

                dst[v]=w+dst[lasti];

            }

        }

        int min_i=0x7f7f7f7f,min_dst=0x7f7f7f7f;

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

        {

            if(!s[i])

            {

                if(dst[i]<min_dst)

                {

                    min_dst=dst[i];

                    min_i=i;

                }

            }

        }

        lasti=min_i;

        s[min_i]=1;

        //printf("更新点%d加入，父节点%d\n",lasti,pre[lasti]);

    }

    cout<<dst[n]<<endl;

    return 0;

}

用dijkstra的模板其实得到的dst[i]就是从1出发的最短路，需要修改的地方在于：

第35,36,37的1全部改成给出的start，然后输出优化一下。

可以先去尝试一下修改模板AC这道题，下面会是完整代码，建议不要直接看哈

.

.

.

.

.

.

…

.

.

.

…

.

.

.

.

#include<bits/stdc++.h>

using namespace std;

int dst[100010];

int n,m;

bool s[100010];

int pre[100010];

struct node

{

    int v,w;

    node(){}

    node(int vv,int ww)

    {

        v=vv,w=ww;

    }

};

vector<node> g[500010];

void init()

{

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

    {

        dst[i]=2147483647;

    }

}

int main()

{

    init();

    int a,b,c,st;

    cin>>n>>m>>st;

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

    {

        cin>>a>>b>>c;

        g[a].push_back(node(b,c));

    }

    s[st]=1;

    dst[st]=0;

    int lasti=st;

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

    {

        for(int j=0;j<g[lasti].size();j++)

        {

            int v=g[lasti][j].v,w=g[lasti][j].w;

            if(!s[v]&&w+dst[lasti]<dst[v])

            {

                pre[v]=lasti;

                dst[v]=w+dst[lasti];

            }

        }

        int min_i=2147483647,min_dst=2147483647;

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

        {

            if(!s[i])

            {

                if(dst[i]<min_dst)

                {

                    min_dst=dst[i];

                    min_i=i;

                }

            }

        }

        if(min_i<=100009)

        {

        	lasti=min_i;

        	s[min_i]=1;

        }

        //printf("更新点%d加入，父节点%d\n",lasti,pre[lasti]);

    }

    cout<<dst[1];

    if(n>1)

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

        {

    	    cout<<" "<<dst[i];

        }

    return 0;

}

ov.

巴特西

【弱化版】【P3371 【模板】单源最短路径（弱化版）】-C++

最新文章

热门文章