スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 2249 Road Construction

ある町に最短で行く経路は複数あり、
そのうち最低のコストのものだけ残せば良い。
そこで最短経路で進んだ場合の
ある町とその一つ前の町をつなぐ道をpreに保存し
preのコストが最小になるように更新していく。

struct road{int to,dist,cost;};

int main(){
while(1){
int n,m;
vector roads[MAX_N];
int dist[MAX_N];
road pre[MAX_N];

scanf("%d%d",&n,&m);
if(!n&&!m)break;

for(int i=0;i int u,v,d,c;
scanf("%d%d%d%d",&u,&v,&d,&c);
roads[u-1].push_back((road){v-1,d,c});
roads[v-1].push_back((road){u-1,d,c});
}

fill(dist,dist+n,INF);
priority_queue, greater

> que;
dist[0] = 0;
que.push(P(0,0));
while(que.size()){
P p = que.top(); que.pop();
int d = p.first;
int pos = p.second;
//cout << pos+1 << endl;
if(d>dist[pos]) continue;
for(int i=0;i int to = roads[pos][i].to;
int co = roads[pos][i].dist + dist[pos];
//cout << pos+1 <<"->" << to+1<< endl;
if(dist[to]>co){
pre[to] = roads[pos][i];
dist[to] = co;
que.push(P(dist[to],to));
}else if(dist[to]==co){
if(pre[to].cost>roads[pos][i].cost){
pre[to] = roads[pos][i];
}
}
}
}

int sum=0;
for(int i=1;i sum += pre[n-i].cost;
}
cout << sum << endl;
}
}

コメントの投稿

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。