2249-Road Construction
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2249
問題概要
頂点数Nの連結な無向グラフが与えられる。
辺はM個ありそれぞれコストと距離の情報を持つ。
頂点番号1からの最短距離が変化しないように、グラフの辺を消去していく。
このときグラフに残る辺のコストの和の最小値を求めよ。
考え方
頂点1からの最短距離を求めていない点に移動する方法のうち最も早く到達し、その中でコストが最も安いものを選択肢追加していく感じのダイクストラ法。
実装(C++)
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> #include <cassert> #include <cwchar> #include <cstdarg> #include <cwctype> #include <queue> #include <stack> #include <algorithm> #include <list> #include <vector> #include <set> #include <map> #include <iostream> #include <deque> #include <complex> #include <string> #include <functional> #include <iomanip> #include <sstream> using namespace std; typedef long long int lli; typedef unsigned int uint; typedef int Weight; const Weight INF=99999999; struct Edge{ int src,dst; Weight cost,distance; Edge(int f,int t,int c,int d){src=f;dst=t;cost=c;distance=d;} }; struct Node:public vector<Edge>{ }; bool operator<(const Edge &a,const Edge &b){ return a.distance!=b.distance?a.cost!=b.cost?a.cost<b.cost:a.dst==b.dst?a.src<b.src:a.dst<b.dst:a.distance<b.distance; } bool operator>(const Edge &a,const Edge &b){return b<a;} typedef vector<Node> Graph; typedef vector<vector<Weight> > Matrix; //隣接行列 typedef pair<int,pair<int,int> > P; //dijkstra法によって問題を解く Weight dijkstra(int s,Graph &G){ int V=G.size(),ac[V],res=0; fill(ac,ac+V,0); ac[s]=true; priority_queue<P,vector<P>,greater<P> > que; for(int i=0;i<G[s].size();i++){ que.push(make_pair(G[s][i].distance,make_pair(G[s][i].cost,G[s][i].dst))); } P t; while(!que.empty()){ t=que.top();que.pop(); if(ac[t.second.second])continue; ac[t.second.second]=true; res+=t.second.first; for(int i=0;i<G[t.second.second].size();i++){ que.push(make_pair(G[t.second.second][i].distance+t.first,make_pair(G[t.second.second][i].cost,G[t.second.second][i].dst))); } } return res; } int main(){ int N,M; for(;scanf("%d%d",&N,&M),N;){ Graph G(N); for(int i=0;i<M;i++){ int a,b,x,y; scanf("%d%d%d%d",&a,&b,&x,&y); a--;b--; G[a].push_back(Edge(a,b,y,x)); G[b].push_back(Edge(b,a,y,x)); } printf("%d\n",dijkstra(0,G)); } return 0; }