JOI2011本戦　第三問「JOI国の買い物事情」

JOI

本戦では迷走してしまった問題orz


町 or 道路上 にある家から一番近いショッピングモールまでの距離の最大値を求めろ、
って問題。

町

まずは各町からショッピングモールまでの最短距離をそれぞれ求めよう。
f:id:snuke:20110215191436p:image
○が町で、中に書いてある数字は町の番号。
数字がオレンジの町はショッピングモールがある町。
青い数字は道の長さ。


ダイクストラ(Dijkstra)を使いましょう。


ダイクストラ法というのは、最短路を計算するアルゴリズムです。
どういうアルゴリズムかというと、
「最短距離が短い頂点から最短距離を確定する」ということを繰り返す
というアルゴリズムです。（今回の場合、頂点＝町 です。）
”確定” をしていくことで、ムダを無くせるのです。
これだけでは分かりにくいと思うので、具体的に説明しましょう。


初期状態で「最短距離が確定している頂点」は頂点２と４で、その距離は０です。
その他の頂点はまだ最短距離が確定していないので、十分に大きな数 INF(=100000001)としておきます。
f:id:snuke:20110215201556p:image
今、最短距離が最も短いのは頂点３で、頂点４からの距離が１です。
f:id:snuke:20110215202453p:image
今、最短距離が最も短いのは頂点１で、頂点４からの距離が２です。
f:id:snuke:20110215202727p:image
とまあこんな感じです。
例では少しスケールが小さいですが、同様にしていけばスケールが大きくても大丈夫です。
priority queueを使って実装するのが普通だと思います。
もし納得がいかないなら、コメント欄で質問するか、表紙にあr(ry を読んで下さい。


これで、各町からショッピングモールまでの最短距離は求められました。
町 i からショッピングモールまでの最短距離を、v[i] としておきましょう。

道路

道路は次の２パターンに分けられます。

  1. ある町〜ショッピングモールの最短経路に含まれている。
  2. 〃　　　　　　　　　含まれていない。

①の例はさっきの図の、4-3, 3-1。（i-j は、町i と町j を結ぶ道を表す事にする。）
②の例はさっきの図の、1-2, 2-3, 2-4。
①の場合、その道路上で一番ショッピングモールから遠い点は頂点。
②の場合、例えば 1-2 の場合、
道路上の１点からショッピングモールまでの距離をグラフにするとこうなります。
f:id:snuke:20110215210943p:image
グラフの交点の場所が、その道路上で一番ショッピングモールから遠い点となります。
その距離を式で表すと、

  • (v[1] + v[2] + 道の長さ) / 2

となります。
「四捨五入せよ」という条件があるので、

  • (v[1] + v[2] + 道の長さ + 1) / 2

とするとうまくいきます。


ここで、①の場合を考え直してみます。
例えば 3-1 の場合、v[1] = v[3] + 道(3-1)の長さ ですよね？
これを②の場合で導いた式に代入しましょう。

  • (v[3] + (v[3] + 道の長さ) + 道の長さ) / 2

これを計算すると、

  • v[3] + 道の長さ

となり、それは v[1] にほかなりません！
というわけで、①の場合にもこの式は適用できます。


これで、ソースコードが組めます。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
#define p1 first
#define p2 second
using namespace std;
typedef pair<int,int> P;

const int INF = 100000001;

struct e{int t, d;};
struct road{int f, t, d;};

vector<e> p[3001];
vector<road> ro;
int v[3001];

int main(){
	int n, m, k, a, b, l, s, ans = 0;
	P x;
	scanf("%d%d%d", &n, &m, &k);
	
	priority_queue<P, vector<P>, greater<P> > q;
	
	rrep(i,n) v[i] = INF;
	rep(i,m){
		scanf("%d%d%d", &a, &b, &l);
		p[a].pb((e){b,l}); p[b].pb((e){a,l});
		ro.pb((road){a,b,l});
	}
	rep(i,k){
		scanf("%d", &s);
		q.push(P(0,s));
	}
	
	while (!q.empty()) {
		x = q.top(); q.pop();
		if(v[x.p2] == INF){
			v[x.p2] = x.p1;
			rep(i,p[x.p2].size()) q.push(P(x.p1 + p[x.p2][i].d, p[x.p2][i].t));
		}
	}
	
	rep(i,ro.size()) ans = max(ans, (v[ro[i].f] + v[ro[i].t] + ro[i].d + 1) / 2);
	
	printf("%d\n",ans);
	
	return 0;
}

〜構造体説明〜
e : ある町から出ている道を記録します。t は"to"で 目的地、d は"distance"で 道の長さ。
road : そのまんま「道」です。f は"from"で 出発点、あとは上に同じ。

〜変数説明〜
p : ある町から出ている道を記録します。
ro : 道の情報を記録します。
v : ある町とショッピングモールの最短距離
n, m, k, a, b, l, s : 入力用
ans : 答え
x : qの内容をいったん避難させるための変数


q : ダイクストラ実装用のpriority queue。型はpair　firstは距離、secondは町の番号


〜おまけ〜
本戦で産まれた、×(ﾊﾞﾂ)ソース
meiso — Gist