SRM 622 Div1 250 BuildingRoutes

2014-05-29

12:38 |

N 頂点、重複しないNxN辺(辺の長さ1〜9, 自分→自分は0)の有向グラフが与えられる。f(辺) = (始点, 終点)の組のうち、その最短経路がその辺を通りうるような組がT個以上あるなら辺の長さ、そうでなければ0　として、f(辺) の和を求めよ。
2≦N≦50

まずWFして...
複数ありうる最短経路がどこを通るかはどうやって分かるんだ？
...
f(s, e) ... s〜eの最短経路で通りうる辺を塗る関数を定義して再帰させる
TLE

(あとで)

他の人のをいくつか見るに,
i→jの最短経路を w[i][j] として、辺ii→jjがi→jの最短経路に含まれるかどうかは
w[i][j] == w[i][ii] + 辺の長さ[ii][jj] + w[jj][j] かどうかで分かる
言われてみればその通りだ。く〜

accepted in practice room

class BuildingRoutes {
	public:
	int build(vector <string> D, int T) {
		int N=D.size();
		VVI d(N, VI(N));
		VVI w(N, VI(N));
		REP(i, N)REP(j,N)d[i][j]=w[i][j]=D[i][j]-'0';
		REP(k,N)REP(i, N)REP(j,N) w[i][j]=min(w[i][j], w[i][k]+w[k][j]);
		ll ans = 0;
		REP(i, N)REP(j,N){
			ll v=0; //(本文中とはi/ii, j/jjが逆)
			REP(ii, N)REP(jj,N) if(w[ii][i]+d[i][j]+w[j][jj]==w[ii][jj]) v++;
			if(v>=T) ans+=d[i][j];
		}
		return ans;
	}
};