码迷元首 @ 2022-09-19 19:08:08
#include<bits/stdc++.h>
struct side
{
int to, w;
};
struct node
{
int u, w;
bool operator <(node b) const
{
return w < b.w;
}
};
int n, m, dis[100001], s;
std::vector<side> graph[100001];
bool vis[100001];
std::priority_queue<node> h;
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u].push_back(side{v, w});
}
memset(dis,0x7f7f7f7f,sizeof(dis));
dis[s] = 0;
h.push(node{s, 0});
while (!h.empty())
{
int x = h.top().u;
h.pop();
if(vis[x])continue;
vis[x]=1;
for (int i = 0; i < graph[x].size(); i++)
{
int y = graph[x][i].to,w=graph[x][i].w;
if (dis[y] > dis[x] + w)
{
dis[y] = dis[x] + w;
if(!vis[y])h.push(node{y, dis[y]});
}
}
}
for (int i = 1; i <= n; i++)printf("%d ", dis[i]);
}
by 码迷元首 @ 2022-09-19 19:12:51
哦哦,把w<b.w改成w>b.w就a了