[TIOJ] 1290. F.不定向邊

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

---

不難發現在走最短路徑的時候不可能會同一邊走兩次(或以上)，所以本題其實直接寫個dijkstra就好了XD

#include <stdio.h>
#include <vector>
#include <queue>
#include <bitset>
typedef unsigned long long llu;

using namespace std;

struct node{
	int to;
	llu val;
};

struct dian{
	int me;
	llu val;
};

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

vector<node> graph[1000 + 10];
bitset<1000 + 10> poped;
llu dis [1000 + 10];

int main(){
	int V, E;
	while(scanf("%d %d",&V,&E)!=EOF){
		priority_queue<dian,vector<dian>,cmp> pq;
		poped.reset();
		for(int i=0;i<1010;i++){
			graph[i].clear();
			dis[i] = 2147483648;
		}
		int start, end;
		scanf("%d %d",&start,&end);
		for(int i=0;i<E;i++){
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			node k;
			k.val=c;
			k.to=b;
			graph[a].push_back(k);
			k.to=a;
			graph[b].push_back(k);
		}
		dis[start] = 0;
		dian DD;
		DD.val = dis[start];
		DD.me = start;
		pq.push(DD);
		while(!pq.empty()){
			dian inPQ = pq.top();
			pq.pop();
			if(poped[inPQ.me]) continue;
			poped[inPQ.me]=1;
			if(inPQ.me == end) break;
			for(int i=0;i<graph[inPQ.me].size();i++){
				node myG = graph[inPQ.me][i];
				if(inPQ.val + myG.val < dis[myG.to]){
					dis[myG.to] = inPQ.val + myG.val;
					dian toPQ;
					toPQ.val = dis[myG.to];
					toPQ.me = myG.to;
					pq.push(toPQ);
				}
			}
		}
		if(dis[end] == 2147483648)
			puts("He is very hot");
		else
			printf("%d\n",dis[end]);
	}
	return 0;
}