本地IDE过了,用的是DEV-C++,编译器是-std=c++14
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5+10, M = 2e5+10;
const int INF = 0x3f3f3f3f;
int dis[N], n, m;
bool tag[N];
vector<pair<int, int> >g[N];
struct node
{
int id, w;
friend operator < (const node &n1, const node &n2)
{
return n1.w > n2.w;
}
};
priority_queue<node>q; // 堆优化
inline void Dijkstra(int s) // O(n log n)
{
for(int i = 1;i <= n;++i)
{
dis[i] = INF;
tag[i] = 0;
}
dis[s] = 0;
for(int i = 1;i <= n;++i)
q.push((node){i, dis[i]});
int cnt = 0;
while(cnt < n)
{
node cur;
while(q.size())
{
cur = q.top();
q.pop();
if(cur.w == dis[cur.id] && !tag[cur.id])
break;
}
tag[cur.id] = 1;
cnt++;
for(auto v : g[cur.id])
{
if(!tag[v.first])
{
dis[v.first] = min(dis[v.first], dis[cur.id]+v.second);
q.push((node){v.first, dis[v.first]});
}
}
}
}
int main()
{
int s, u, v, w;
scanf("%d%d%d", &n, &m, &s);
while(m--)
{
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(make_pair(v, w));
}
Dijkstra(s);
for(int i = 1;i <= n;++i)
cout << dis[i] << " ";
return 0;
}