AOJ 2249 Road Construction

Road Construction | Aizu Online Judge

与えられた無向グラフで、長さ優先で、次にコスト最小のグラフをつくりたい。辺ごとに維持費みたいなのがあって、最低で必要なコストを求めなさい。(長さは元の最短と同じじゃないとだめ)

よくわからない。あまりイメージできてない。

決して簡単な問題じゃないんだろうけど、適当に書いてみたらなんか通ってしまった。

謎ダイクストラ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
struct NODE{
	int to , dist , cost;
	NODE(int a,int b,int c){
		to = a , dist = b , cost = c;
	}
};
bool operator < (const NODE &a,const NODE &b){
	return a.dist != b.dist ? a.dist > b.dist : a.cost > b.cost;
}
int main(){
	int n,m;
	while(cin >> n >> m && (n||m) ){
		vector< vector<NODE> > g(n);
		bool done[10000] = {0};
		int ans = 0;
		rep(i,m){
			int a,b,c,d;
			cin >> a >> b >> c >> d;
			a--,b--;
			g[a].push_back(NODE(b,c,d));
			g[b].push_back(NODE(a,c,d));
		}
		priority_queue <NODE> Q;
		Q.push(NODE(0,0,0));
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if(done[q.to])continue;
			else done[q.to] = true , ans += q.cost;
			rep(i,g[q.to].size()) Q.push(NODE(g[q.to][i].to,q.dist+g[q.to][i].dist,g[q.to][i].cost));
		}
		cout << ans << endl;
	}
}