Submission #1129435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129435		ChuanChen	Commuter Pass (JOI18_commuter_pass)	C++20	24 / 100	33 ms	1160 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int lim = 3e2+5;
const ll inf = 1e18;

int n, m, S, T, U, V;
ll ans = inf;

// struct Edge{
// 	int a, b, c;
// };
// Edge edges[2*lim];
// vector<int> adj[lim], weight[lim], idx[lim];

ll d[lim][lim];
void addEdge(int a, int b, int c, int i){
	d[a][b] = c;
	d[b][a] = c;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	cin >> S >> T >> U >> V;
	assert(n <= 300);

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			d[i][j] = inf;
		}
		d[i][i] = 0;
	}
	for(int i = 1; i <= m; i++){
		int a, b, c; cin >> a >> b >> c;
		addEdge(a, b, c, i);
	}

	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				d[i][j] = min(d[i][j], d[i][k]+d[j][k]);
			}
		}
	}
	ans = d[U][V];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(d[S][i] + d[i][j] + d[j][T] == d[S][T]){
				ans = min({ans, d[U][i]+d[j][V], d[V][i]+d[j][U]});
			}
		}
	}
	cout << ans << '\n';

}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45