输出dijkstra最短路路径


1


1

输出dijkstra最短路路径

题目描述:给定一个n个点,m条有向边的带非负权图,请你计算从s出发到r号点的最短路径。
输入格式:第一行为三个正整数n,m,s,r。第二行起m行,每行三个非负整数u,v,w,表示从
u到v有一条权值为w的有向边。
输出格式:输出s到r号点的最短路径,如果有多条最短路径,输出任意一条路径均可。如果无法到达r,输出-1

应该是可以用堆优化版本的dijkstra最短路模板去改，但是我改出来的代码最基本的样例(自己构造的数据都过不去)
错误的代码:

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,s,r;
const int N=4e5+10;
const int INF=0x3f3f3f3f;

typedef pair<int, int> PII;

int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到s号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
int cnt;
int g[N];//记录路径 

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}

//求s号点到r的最短路径 
void dijkstra()
{
    for(int i=0;i<=n;i++)
    {
        dist[i]=1e11;
    }
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,s});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i!= -1; i = ne[i])
        {
            int j = e[i];
            if(i==r) break;
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
                g[++cnt]=j;
            }
        }
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    cin>>n>>m>>s>>r;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();

    for(int i=1;i<=n;i++)
    {
        cout<<dist[i]<<" ";
    }
    cout<<endl;
    if(dist[r]>=1e11/2) 
    {
        cout<<-1;
        return 0;
    }

    //输出s到r号点的最短路径
    cout<<s<<' ';
    for(int i=1;i<=cnt-1;i++)
    {
        cout<<g[i]<<" ";
    }
    cout<<r;
}

不知道哪位大神能帮忙修改，万分感谢!

dijkstra

提问于4个月前
3663


2 个问答


2

不好意思，dijkstra中的if(i==r)我忘了删了

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,s,r;
const int N=(4e5+10) * 2;
const int INF=0x3f3f3f3f;

typedef pair<int, int> PII;

int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int h2[N];  //  存反向图
int dist[N];        // 存储所有点到s号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
int cnt;
int g[N];

void add(int h[], int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}

//求s号点到r的最短路径 
void dijkstra()
{
    for(int i=0;i<=n;i++)
    {
        dist[i]=1e11;
    }
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,s});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;
        // cout<<ver<<" "<<distance<<endl;
        for (int i = h[ver]; i!= -1; i = ne[i])
        {
            int j = e[i];
            //  cout<<"-- "<<j<<" "<<dist[j]<<endl;
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

inline void dfs(int u)
{
    for(int i=h2[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==s){
            g[cnt++] = s;
            return;
        }else if(dist[u] == dist[j] + w[i]){
            dfs(j);
            g[cnt++] = j;
            return;
        }
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof(h));
    memset(h2, -1, sizeof h2);

    cin>>n>>m>>s>>r;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(h,x,y,z);add(h2,y,x,z);
    }
    dijkstra();

    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dist[i]<<" ";
    // }
    // cout<<endl;
    if(dist[r]>=1e11/2) 
    {
        cout<<-1;
        return 0;
    }

    //输出s到r号点的最短路径
    cout<<dist[r]<<endl;

    dfs(r);
    for(int i=0;i<cnt;i++) cout<<g[i]<<" ";

    cout<<r;
}
回答于4个月前
31009
🥰 –  啼莺修竹   4个月前
万分感谢！手搓了几个数据都没有问题。 –  zhangyuxuan   4个月前

1

我按照我的理解，应该是这样的，有什么的不对的地方请指正。dijkstra中j=e[i]的下面应该是j==r，输出s到r的最短路径应输出dist[r]，不是s。而且不能直接将所有的点都放进g数组中，因为s到r的最短路中不一定包含这个点。可以建一个反向图，先用dijkstra，再dfs，看当前这个点是由哪个点转移来的。代码如下:
#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,s,r;
const int N=(4e5+10) * 2;
const int INF=0x3f3f3f3f;

typedef pair<int, int> PII;

int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int h2[N];  //  存反向图
int dist[N];        // 存储所有点到s号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
int cnt;
int g[N];

void add(int h[], int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}

//求s号点到r的最短路径 
void dijkstra()
{
    for(int i=0;i<=n;i++)
    {
        dist[i]=1e11;
    }
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,s});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i!= -1; i = ne[i])
        {
            int j = e[i];
            if(i==r) break;
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

inline void dfs(int u)
{
    for(int i=h2[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==s){
            g[cnt++] = s;
            return;
        }else if(dist[u] == dist[j] + w[i]){
            dfs(j);
            g[cnt++] = j;
            return;
        }
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof(h));
    memset(h2, -1, sizeof h2);

    cin>>n>>m>>s>>r;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(h,x,y,z);add(h2,y,x,z);
    }
    dijkstra();

    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dist[i]<<" ";
    // }
    // cout<<endl;
    if(dist[r]>=1e11/2) 
    {
        cout<<-1;
        return 0;
    }

    //输出s到r号点的最短路径
    cout<<dist[r]<<endl;

    dfs(r);
    for(int i=0;i<cnt;i++) cout<<g[i]<<" ";

    cout<<r;
}
回答于4个月前
31009
你好,输入数据: 4 4 1 4 1 4 1000 1 2 10 2 3 10 3 4 10 正确的输出应该是 30 1 2 3 4 但是按照程序的输出结果是: 1000 1 4 –  zhangyuxuan   4个月前
我来回答