이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
struct datax{
ll u, v, w;
};
ll n, m, k, cities[100005], ans, t, u, v, w, dist[100005], h[100005];
ll flat[100005], d[505][505], f[505], g[505];
vector<ii> adj[100005];
datax queries[400005];
bool check(ll x, ll y, ll z, ll t){
return (x!=y&&x!=z&&x!=t&&y!=z&&y!=t&&z!=t);
}
void dijkstra(ll s){
priority_queue<ii, vector<ii>, greater<ii>> pq;
for(int i=1; i<=n; i++) dist[i] = 1e9;
dist[s] = 0;
pq.push({0, s});
while(!pq.empty()){
ll val = pq.top().fi;
ll u = pq.top().se;
pq.pop();
if(dist[u]!=val) continue;
for(auto edge:adj[u]){
ll v = edge.fi;
ll w = edge.se;
if(dist[v]>dist[u]+w){
dist[v] = dist[u]+w;
pq.push({dist[v], v});
}
}
}
}
void dijkstra2(){
priority_queue<ii, vector<ii>, greater<ii>> pq;
for(int i=1; i<=n; i++) dist[i] = 1e9;
for(int i=1; i<=k; i++){
dist[cities[i]]=0;
pq.push({0, cities[i]});
h[cities[i]] = cities[i];
}
while(!pq.empty()){
ll val = pq.top().fi;
ll u = pq.top().se;
pq.pop();
if(dist[u]!=val) continue;
for(auto edge:adj[u]){
ll v = edge.fi;
ll w = edge.se;
if(dist[v]==dist[u]+w) flat[v] = 1;
if(dist[v]>dist[u]+w){
dist[v] = dist[u]+w;
h[v] = h[u];
flat[v]=0;
pq.push({dist[v], v});
}
}
}
}
void inp(){
cin >> n >> m >> k;
for(int i=1; i<=m; i++){
cin >> u >> v >> w;
queries[i] = {u, v, w};
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(int i=1; i<=k; i++) cin >> cities[i];
}
void sub1(){
ll ans=LLONG_MAX;
for(int i=1; i<=n; i++){
dijkstra(i);
for(int j=1; j<=n; j++)
d[i][j] = dist[j];
}
for(int x=1; x<=k; x++){
for(int y=1; y<=k; y++){
for(int z=1; z<=k; z++){
for(t=1; t<=k; t++){
if(check(x, y, z, t)){
ans = min(ans, d[cities[x]][cities[y]]+d[cities[z]][cities[t]]);
}
}
}
}
}
cout << ans;
}
void sub2(){
for(int i=1; i<=n; i++){
dijkstra(i);
for(int j=1; j<=n; j++)
d[i][j] = dist[j];
f[i] = cities[1];
g[i] = cities[1];
if(i==cities[1]){
f[i] = cities[2];
g[i] = cities[2];
}
}
//cout << d[3][1] << '\n';
for(int i=1; i<=k; i++){
for(int j=1; j<=k; j++){
if(i==j) continue;
ll x = cities[i];
ll y = cities[j];
if(d[x][y]<d[x][f[x]]){
f[x]=y;
}
else{
if(d[x][y]<d[x][g[x]]){
g[x]=y;
}
}
}
//cout << f[cities[i]] << '\n';
}
ll ans=LLONG_MAX;
for(int i=1; i<=k; i++){
for(int j=i+1; j<=k; j++){
ll x = cities[i];
ll y = cities[j];
if(f[x]!=f[y]&&f[x]!=y&&f[y]!=x) ans = min(ans, d[x][f[x]]+d[y][f[y]]);
else
if(g[x]!=y&&f[y]!=x) ans = min(ans, d[x][g[x]]+d[y][f[y]]);
if(f[x]!=y&&g[y]!=x) ans = min(ans, d[x][f[x]]+d[y][g[y]]);
}
}
cout << ans;
}
void sub3(){
dijkstra2();
ll ans=LLONG_MAX;
for(int i=1; i<=m; i++){
ll u = queries[i].u, v = queries[i].v, w = queries[i].w;
if(u==1||u==2) continue;
if(flat[u]||flat[v]||h[u]!=h[v]){
ans = min(ans, dist[u]+dist[v]+w);
//cout << dist[u] << ' ' << dist[v] << '\n';
//cout << flat[u] << ' ' <<flat[v] << '\n';
}
}
cout << ans+1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
//freopen("cities.inp", "r", stdin);
//freopen("cities.out", "w", stdout);
inp();
if(n<=50) sub1();
else if(n<=500&&m<=4000) sub2();
else sub3();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
RelayMarathon.cpp: In function 'void sub2()':
RelayMarathon.cpp:139:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
139 | else
| ^~~~
RelayMarathon.cpp:141:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
141 | if(f[x]!=y&&g[y]!=x) ans = min(ans, d[x][f[x]]+d[y][g[y]]);
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |