这套dijkstra在别的题测没啥问题,这题的数据咋就不过了呢?
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> node;
const int MAX = 200010;
const int INF = (1 << 21) ;
struct cmp{
bool operator()(node a, node b){
return a.second > b.second;
}
};
node P(int a, int b){
return make_pair(a, b);
}
int n;
vector<node> map[MAX];
void dijkstra(int s){
priority_queue<node, vector<node>, cmp> PQ;
int cost[MAX];
bool confirm[MAX];
for (int i = 1; i <= n; i++){
cost[i] = INF;
confirm[i] = false;
}
cost[s] = 0;
PQ.push(P(s, 0));
while (!PQ.empty()){
node f = PQ.top(); PQ.pop();
int u = f.first;
confirm[u] = true;
if (cost[u] < f.second) continue;
for (int i = 0; i < map[u].size(); i++){
int v = map[u][i].first;
int c = map[u][i].second;
if (confirm[v]) continue;
if (cost[v] > cost[u] + c) {
cost[v] = cost[u] + c;
PQ.push(P(v, cost[v]));
}
}
}
for (int i = 1; i <= n; i++)
cout << cost[i] <<" ";
cout << endl;
}
int main(){
int m, s, u, v, c;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++){
cin >> u >> v >> c;
map[u].push_back(P(v, c));
}
dijkstra(s);
return 0;
}