输出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