萌新刚学Dijkstra
查看原帖
萌新刚学Dijkstra
117662
那一条变阻器楼主2020/6/19 16:46

wa1点re234点

#include <bits/stdc++.h>
using namespace std;
int n , m , s;
int vis[100010] , dis[100010];
vector<pair<int , int> > e[100010];
priority_queue<pair<int , int> > q;
void dijkstra(){
	dis[1] = 0;
	vis[1] = 1;
	q.push(make_pair(0 , 1));
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		for(int i = 0; i < e[x].size(); i++){
			int nx = e[x][i].second , y = e[x][i].first;
			if(dis[nx] > dis[x] + y){
				dis[nx] = dis[x] + y;
				if(!vis[nx]){
					vis[nx] = 1;
					q.push(make_pair(-dis[y] , nx));
				}
			}
		}
	}
}
int main(){
	cin >> n >> m >> s;
	for(int i = 1; i <= n; i++) dis[i] = 0x3ffffff;
	for(int i = 1; i <= m; i++){
		int x , y , z;
		cin >> x >> y >> z;
		e[x].push_back(make_pair(z , y));
	}
	dijkstra();
	for(int i = 1; i <= n; i++) cout << dis[i] << " ";
	return 0;
}
2020/6/19 16:46
加载中...