萌新求助,WA了1,3,4,5四个点
查看原帖
萌新求助,WA了1,3,4,5四个点
90763
Disviel楼主2020/11/8 23:34

这套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;
}
2020/11/8 23:34
加载中...