AOJ 0562 Shopping in JOI Kingdom

• 概要

日本語の問題なので省略させていただきます。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562

最近AOJがWAのデータとか見せてくれるのでありがたいですね。

• 解法

まず各ショッピングモールのある町からダイクストラ法を用いてすべての町への最短距離を求めます。

次に町と町の間にある家に対してへの求め方は

赤点,青点:町

黒いの:辺

だと思ってください(見えないとか言わないで)

赤点からショッピングモールまでの最短距離をA、

青点からショッピングモールまでの最短距離をBとします。

もしAとBが異なる値だった場合、赤点と青点を繋ぐ辺を分割する位置は中央に定まりません。

なので以下の式で求めます。

A>Bであるとき　A+(B-A)+(辺の重み-(B-A))/2.0

どうしてこの式に至るかは少し考えればわかると思います。

この式で求まった最大の値を四捨五入ものが解になります。

#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<cstdlib>
#include<queue>
#include<cmath>
#define MAX_D 3000
#define INF 0x8ffffff

using namespace std;
typedef pair<int,int> P;

int main()
{	
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	vector<P> edge[MAX_D];

	for(int i=0;i<m;i++){
		int a,b,l;scanf("%d%d%d",&a,&b,&l);
		edge[a-1].push_back(make_pair(b-1,l));
		edge[b-1].push_back(make_pair(a-1,l));
	}
	
	int D[MAX_D];
	fill(D,D+n,INF);
	priority_queue<P> que;
	for(int i=0;i<k;i++){
		int p;scanf("%d",&p);
		D[p-1]=0;
		que.push(make_pair(0,p-1));
	}

	while(!que.empty()){
		P q=que.top();que.pop();
		int v=q.second;
		if(D[v]<q.first)continue;
		for(int i=0;i<edge[v].size();i++){
			P e=edge[v][i];
			if(D[e.first]>D[v]+e.second){
				D[e.first]=D[v]+e.second;
				que.push(make_pair(D[e.first],e.first));
			}
		}
	}

	double ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<edge[i].size();j++){
			P v=edge[i][j];
			int diff=D[v.first]-D[i];
			if(diff<0.0)continue;
			double g=D[i]+diff+(v.second-diff)/2.0;
			ans=ans<g?g:ans;
		}
	}

	printf("%.0lf\n",round(ans));
	return 0;
}

VC++2010で出力するとround関数使わなくても四捨五入しやがってくれたのでさげぽよ