WA on #4 求条

// Problem: Luogu P1841
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1841
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define N 205
#define int long long
#define INF 1e18
using namespace std;

int n,m;
int dp[N][N];
vector<int> done[N][N];
set<int> ans;

void init(){
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			dp[i][j] = INF;
		}
	}
	
	// 初始化对角线
	for (int i=1;i<=n;++i) dp[i][i] = 0;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	
	init();
	
	for (int i=1;i<=m;++i){
		int a,b,w;cin >> a >> b >> w;
		dp[a][b] = w;
		dp[b][a] = w;
	}
	
	for (int k=1;k<=n;++k){
		for (int i=1;i<=n;++i){
			for (int j=1;j<=n;++j){
				if (i == k || j == k) continue;// 不重点
				int cnt = dp[i][k] + dp[k][j];
				if (cnt < dp[i][j]){
					dp[i][j] = cnt;
					done[i][j].clear();
					done[i][j].push_back(k);
				}
				else if (cnt == dp[i][j]) done[i][j].push_back(k);
			}
		}
	}
	
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			if (done[i][j].size() == 1){
				ans.insert(done[i][j][0]);
			}
		}
	}
	
	if (ans.size()) for (int d : ans) cout << d << ' ';
	else cout << "No important cities.";
	
	
	return 0;
}