제출 #1023610

#제출 시각아이디문제언어결과실행 시간메모리
1023610vjudge1Robot (JOI21_ho_t4)C++17
100 / 100
154 ms96696 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define ull unsigned long long #define pii pair<int,int> #define pll pair<long long, long long> #define fi first #define se second #define all(a) (a).begin(), (a).end() #define pb push_back #define lwb lower_bound #define upb upper_bound #define TASKNAME "NAME" void init() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout); } const int SZ = 2e6+5; const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18; const double epsilon = 1e-3; int n,m; struct Edge { int v, c; ll p; Edge(int _v = 0, int _c = 0, ll _p = 0) : v(_v), c(_c), p(_p) {} }; vector<Edge> adj[SZ]; ll dp[SZ], sum[SZ], mn[SZ]; struct Node { int u; ll d; Node(int _u = 0, ll _d = 0) : u(_u), d(_d) {} bool operator < (const Node& other) const { return d > other.d; } }; priority_queue<Node> pq; int main() { init(); cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v, c; ll p; cin >> u >> v >> c >> p; adj[u].pb({v, c, p}); adj[v].pb({u, c, p}); } for(int i = 1; i < SZ; i++) { dp[i] = INFLL; mn[i] = INFLL; } dp[1] = 0; pq.push({1, 0}); while(!pq.empty()) { int u = pq.top().u; ll d = pq.top().d; pq.pop(); if(d > dp[u]) continue; for(Edge e : adj[u]) { int v = e.v, c = e.c; ll p = e.p; mn[c] = min(mn[c], dp[v]); sum[c] += p; } for(Edge e : adj[u]) { int v = e.v, c = e.c; ll p = e.p; if(dp[v] > dp[u] + min(p, sum[c] - p)) { dp[v] = dp[u] + min(p, sum[c] - p); pq.push({v, dp[v]}); } if(dp[v] > mn[c] + sum[c] - p ) { dp[v] = mn[c] + sum[c] - p; pq.push({v, dp[v]}); } } for(Edge e : adj[u]) { int v = e.v, c = e.c; ll p = e.p; mn[c] = INFLL; sum[c] -= p; } } cout << (dp[n] == INFLL ? -1 : dp[n]); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:103:17: warning: unused variable 'v' [-Wunused-variable]
  103 |             int v = e.v, c = e.c;
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...