社区讨论
堆优化dijkstra求助
P4779【模板】单源最短路径(标准版)参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @loc1ezjr
- 此快照首次捕获于
- 2023/10/30 06:23 2 年前
- 此快照最后确认于
- 2023/11/04 11:57 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
typedef pair<int ,int > PII;
const int maxn=150010;
int n,m;
int h[maxn],e[maxn],ne[maxn],w[maxn],idx;
bool st[maxn];
int dist[maxn];
inline void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
inline int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue< PII, vector < PII > , greater < PII > > heap;
heap.push({0,1});
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 (dist[j]>distance+w[i])
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if (dist[n]==0x3f3f3f3f) return -1;else
return dist[n];
}
int main(){
memset(h,-1,sizeof h);
int k;
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=dijkstra();
for(int i=1;i<=n;i++)
cout<<dist[i]<<" ";
}
麻烦大佬救救孩子。。。
回复
共 5 条回复,欢迎继续交流。
正在加载回复...