ikun_fjh @ 2023-07-13 21:04:40
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5+5;
struct Edge{
int y;
int w;
};
struct Node {
int y, d;
bool operator < (const Node &n1) const {
return d > n1.d;
}
};
long long n , m , s , x , y , w;
vector<Edge> g[N];
long long d[N];
bool vis[N];
priority_queue<Node , vector<Node> , less<Node> > q;
void dijkstra(int sx)
{
memset(d , 0x7f , sizeof(d));
memset(vis , false , sizeof(vis));
d[sx] = 0;
q.push((Node) {sx,0});
while(!q.empty())
{
Node n1 = q.top();
int x = n1.y;
q.pop();
if(vis[x] == true)
{
continue;
}
vis[x] = true;
for(int i = 0 ; i < g[x].size(); i++)
{
Edge nxt = g[x][i];
int y = nxt.y;
int w = nxt.w;
if(vis[y]) continue;//
if(d[x]+w < d[y])
{
d[y] = d[x] + w;
//d[y] = min(d[y] , d[x]+w);
q.push((Node) {y, d[y]});
}
}
}
}
int main()
{
scanf("%d%d%d" , &n , &m , &s);
//memset(a , 0x3f , sizeof(a));
for(int i = 1 ; i <= m ; i++)
{
scanf("%d%d%d" , &x , &y , &w);
g[x].push_back((Edge){y , w});
}
dijkstra(s);
for(int i = 1 ; i <= n ; i++)
{
cout << d[i] << " ";
}
return 0;
}
求助大佬,为什么28行greater改less还能过?
by Claire0918 @ 2023-07-13 21:07:53
@fujiahe 堆优化只是优化,不一定要有。如果数据大一点就不行了。
by WsW_ @ 2023-07-13 21:14:02
@fujiahe 堆优化只是优化
你这相当于反向优化,使时间更劣,但能过
by ikun_fjh @ 2023-07-13 21:48:35
懂了,谢谢dalao