[TIOJ]1509. 地道問題

題目連結:http://tioj.infor.org/problems/1509

---

裸單點源最短路徑，直接寫個dijkstra就好了

#include <stdio.h>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>

using std::vector;
using std::priority_queue;
using std::bitset;
using std::swap;

struct node{
	int vertex;
	int dis;
};

class cmp{
public:
	bool operator ()(node a, node b){
		return a.dis>b.dis;
	}
};

bitset<1000000 + 10> poped;
vector<node> forward[1000000 + 10], backward[1000000 + 10];
int dis[1000000 + 10];
priority_queue<node,vector<node>,cmp> pq;

int main(){
	//input
	int m,n;
	unsigned long long ans=0;
	scanf("%d %d",&m,&n);
	for(int i=0;i<n;i++){
		node OAO;
		int a;
		scanf("%d %d %d",&a,&OAO.vertex,&OAO.dis);
		forward[a].push_back(OAO);
		swap(a,OAO.vertex);
		backward[a].push_back(OAO);
	}
	for(int i=0;i<=m;i++){
		dis[i] = 2147483647;
	}
	dis[1] = 0;
	node f;
	f.dis = dis[1];
	f.vertex = 1;
	pq.push(f);
	while(!pq.empty()){
		node k = pq.top();
		pq.pop();
		if(poped[k.vertex]) continue;
		poped[k.vertex] = 1;
		for(int i=0;i<forward[k.vertex].size();i++){
			node n;
			n.vertex = forward[k.vertex][i].vertex;
			n.dis = k.dis + forward[k.vertex][i].dis;
			if(n.dis < dis[n.vertex]){
				dis[n.vertex] = n.dis;
				pq.push(n);
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(dis[i]==2147483647){
			puts("0");
			exit(0);
		}else{
			ans += dis[i];
			dis[i] = 2147483647;
		}
	}
	poped.reset();
	dis[1] = 0;
	f.dis = dis[1];
	f.vertex = 1;
	pq.push(f);
	while(!pq.empty()){
		node k = pq.top();
		pq.pop();
		if(poped[k.vertex]) continue;
		poped[k.vertex] = 1;
		for(int i=0;i<backward[k.vertex].size();i++){
			node n;
			n.vertex = backward[k.vertex][i].vertex;
			n.dis = k.dis + backward[k.vertex][i].dis;
			if(n.dis < dis[n.vertex]){
				dis[n.vertex] = n.dis;
				pq.push(n);
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(dis[i]==2147483647){
			puts("0");
			exit(0);
		}else{
			ans += dis[i];
		}
	}
	printf("%llu",ans);
	return 0;
}