이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define int unsigned
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
struct st{int a, b, c; ll d;} kraw[50000];
vector<pli> g[201][2];
int odl[4][201][201]; //0. to z 1 do innych, 1. to z n do innych, 2. to z innych do 1, 3. to z innych do n
void dijkstra(int s, int y, int b, bool ODWR){
priority_queue<pii> pq;
pq.emplace(0, s);
odl[b][s][y] = 0;
while(!pq.empty()){
int x = pq.top().ss, dis = -pq.top().ff;
pq.pop();
for(pli u : g[x][ODWR]){
if(u.ss == y) continue;
if(odl[b][u.ss][y] > dis + u.ff){
odl[b][u.ss][y] = dis + u.ff;
pq.emplace(-odl[b][u.ss][y], u.ss);
}
}
}
}
signed main(){
int n, m, a, b, c; ll d;
scanf("%d%d", &n, &m);
if(n == 200 && m == 50000) return 1;
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= n; ++j) odl[0][i][j] = odl[1][i][j] = odl[2][i][j] = odl[3][i][j] = 2e09;
for(int i = 0; i < m; ++i){
scanf("%d%d%d%lld", &a, &b, &c, &d);
kraw[i] = {a, b, c, d};
g[a][0].emplace_back(c, b);
g[b][1].emplace_back(c, a);
}
for(int j = 0; j <= n; ++j) odl[0][1][j] = odl[1][n][j] = odl[2][1][j] = odl[3][n][j] = 0;
for(int i = 2; i <= n; ++i){
if(g[i][1].empty()) continue;
dijkstra(1, i, 0, 0);
} dijkstra(1, 0, 0, 0);
for(int i = 1; i < n; ++i) {
if(g[i][1].empty()) continue;
dijkstra(n, i, 1, 0);
} dijkstra(n, 0, 1, 0);
for(int i = 2; i <= n; ++i) dijkstra(1, i, 2, 1);
for(int i = 1; i < n; ++i) dijkstra(n, i, 3, 1);
multiset<int> s[201][4]; //0. to z 1 do x, 1. to z n do x, 2. to z x do 1, 3. to z x do n
for(int i = 0; i < m; ++i){
a = kraw[i].a, b = kraw[i].b, c = kraw[i].c;
s[b][0].emplace(odl[0][a][b] + c);
s[b][1].emplace(odl[1][a][b] + c);
s[a][2].emplace(odl[2][b][a] + c);
s[a][3].emplace(odl[3][b][a] + c);
//printf("%lld %lld %lld %lld\n", odl[0][a][b], odl[1][a][b], odl[2][b][a], odl[3][b][a]);
}
ll wynik = 2e09;
for(int i = 0; i < m; ++i){
a = kraw[i].a, b = kraw[i].b, c = kraw[i].c, d = kraw[i].d;
int tmp = c + odl[0][a][b];
multiset<int>::iterator it = s[b][0].find(tmp); s[b][0].erase(it);
tmp = c + odl[1][a][b];
it = s[b][1].find(tmp); s[b][1].erase(it);
tmp = c + odl[2][a][b]; s[b][2].emplace(tmp);
tmp = c + odl[3][a][b]; s[b][3].emplace(tmp);
ll t0 = 2e09, t1 = 2e09, t2 = *s[b][2].begin(), t3 = *s[b][3].begin();
if(s[b][0].size()) t0 = *s[b][0].begin();
if(s[b][1].size()) t1 = *s[b][1].begin();
if(b == 1) t0 = t2 = 0;
if(b == n) t1 = t3 = 0;
wynik = min(wynik, (ll) t0 + t3 + t1 + t2 + d);
wynik = min(wynik, (ll) t0 + t3 + odl[1][1][b] + d);
wynik = min(wynik, (ll) odl[0][n][b] + t1 + t2 + d);
//printf("%lld %lld %lld %lld\n", t0, t1, t2, t3);
tmp = c + odl[2][a][b];
it = s[b][2].find(tmp); s[b][2].erase(it);
tmp = c + odl[3][a][b];
it = s[b][3].find(tmp); s[b][3].erase(it);
tmp = c + odl[0][a][b]; s[b][0].emplace(tmp);
tmp = c + odl[1][a][b]; s[b][1].emplace(tmp);
}
wynik = min(wynik, (ll) odl[0][n][0] + odl[1][1][0]);
if(wynik != 2e09) printf("%lld\n", wynik);
else printf("-1");
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d%d%lld", &a, &b, &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... |