이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
int u, v, idx; ll c, d;
Edge(){}
Edge(int u, int v, int idx, ll c, ll d): u(u), v(v), idx(idx), c(c), d(d){}
bool operator==(const Edge &r)const{
return idx == r.idx;
}
};
int n, m;
vector<Edge> link[202];
vector<Edge> revLink[202];
Edge arr[50002];
ll ans = LLONG_MAX;
struct Dijkstra {
int n;
ll dist[202]; int prv[202], start, last;
bool used[50002], chk[202];
void init(int _n, int _start){
n = _n, start = _start, last = n+1-start;
}
void run(){
fill(dist+1, dist+n+1, 1e18);
fill(chk+1, chk+n+1, false);
fill(used+1, used+m+1, false);
dist[start] = 0;
while(1){
int pnt = 0; ll pntD = 1e18;
for(int i=1; i<=n; i++){
if(!chk[i] && pntD > dist[i]) pntD = dist[i], pnt = i;
}
if(pnt == 0) break;
chk[pnt] = 1;
for(auto y: link[pnt]){
int nxt = y.v;
ll nxtCost = dist[pnt] + y.c;
if(nxtCost < dist[nxt]){
dist[nxt] = nxtCost;
prv[nxt] = y.idx;
}
}
}
if(dist[last] == 1e18) return;
int tmp = last;
while(tmp != start){
used[prv[tmp]] = 1;
tmp = arr[prv[tmp]].u;
}
}
} dijk1, dijk2, dijktmp, dijk1rev, dijk2rev;
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int u, v; ll c, d;
scanf("%d %d %lld %lld", &u, &v, &c, &d);
link[u].push_back(Edge(u, v, i, c, d));
revLink[v].push_back(Edge(v, u, i, c, d));
arr[i] = Edge(u, v, i, c, d);
}
dijk1.init(n, 1), dijk1rev.init(n, n), dijk2.init(n, n), dijk2rev.init(n, 1);
dijk1.run(), dijk2.run();
ans = dijk1.dist[n] + dijk2.dist[1];
for(int i=1; i<=n; i++) revLink[i].swap(link[i]);
for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v);
dijk1rev.run();
dijk2rev.run();
for(int i=1; i<=n; i++) revLink[i].swap(link[i]);
for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v);
for(int i=1; i<=m; i++){
ll ret = arr[i].d;
if(!dijk1.used[i]) ret += min(dijk1.dist[n], dijk1.dist[arr[i].v] + dijk1rev.dist[arr[i].u] + arr[i].c);
else{
link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
swap(arr[i].u, arr[i].v);
link[arr[i].u].push_back(arr[i]);
dijktmp.init(n, 1);
dijktmp.run();
ret += dijktmp.dist[n];
link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
swap(arr[i].u, arr[i].v);
link[arr[i].u].push_back(arr[i]);
}
if(!dijk2.used[i]) ret += min(dijk2.dist[1], dijk2.dist[arr[i].v] + dijk2rev.dist[arr[i].u] + arr[i].c);
else{
link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
swap(arr[i].u, arr[i].v);
link[arr[i].u].push_back(arr[i]);
dijktmp.init(n, n);
dijktmp.run();
ret += dijktmp.dist[1];
link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
swap(arr[i].u, arr[i].v);
link[arr[i].u].push_back(arr[i]);
}
ans = min(ans, ret);
}
printf("%lld", ans > 1e17 ? -1 : ans);
}
컴파일 시 표준 에러 (stderr) 메시지
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
66 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d %d %lld %lld", &u, &v, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |