[Round 1B 2017] Problem C. Pony Express : https://code.google.com/codejam/contest/8294486/dashboard#s=p2&a=2 Floyd–Warshall

Pony Express.cpp

//
//  Created by fpdjsns
//  Copyright © 2019 fpdjsns. All rights reserved.
//
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define INF 1e12
typedef long long LL;

using namespace std;

int main() {
	int T;
	cin >> T;
	for (int c = 1; c <= T; c++) {

		/* input */
		int N, Q;
		cin >> N >> Q;
		vector<int> E(N), S(N);
		vector<vector<LL>> D(N, vector<LL>(N));
		vector<int> U(Q), V(Q);
		for (int i = 0; i < N; i++) cin >> E[i] >> S[i];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++){
				cin >> D[i][j];
				if (D[i][j] == -1) D[i][j] = INF;
			}
		for (int i = 0; i < Q; i++) cin >> U[i] >> V[i];

		/* solve */

		// shortest direct
		for (int k = 0; k < N; k++)
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

		// shortest time
		vector<vector<double>> x(N, vector<double>(N, INF));
		
		// time of moving i to j with i'th horse
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++){
				if (E[i] < D[i][j]) continue; // can not move
				else x[i][j] = (double)D[i][j] / S[i];
			}
		for (int k = 0; k < N; k++)
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					x[i][j] = min(x[i][j], x[i][k] + x[k][j]);

		/* output */
		printf("Case #%d: ", c);
		for (int i = 0; i < Q; i++)
			printf("%.6lf ", x[U[i] - 1][V[i] - 1]);
		printf("\n");
	}
	return 0;
}