제출 #1091945

#제출 시각아이디문제언어결과실행 시간메모리
1091945coldbr3wRobot (JOI21_ho_t4)C++17
24 / 100
875 ms117744 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 2e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 350; ll n,m; struct ccjv{int v,c; ll p;}; struct ngu{int u,c; ll col;}; map<int,ll>d[N]; struct cmp{ bool operator()(const ngu &a, const ngu &b){ return a.c > b.c; } }; map<int, vector<ccjv>>g[N]; vector<ccjv>adj[N]; map<ll,ll>mp[N]; void to_thic_cau(){ cin >> n >> m; for(int i = 1; i <= m;i++){ ll u,v,c,p; cin >> u >> v >> c >> p; mp[u][c] += p; mp[v][c] += p; adj[u].pb({v,c,p}); adj[v].pb({u,c,p}); g[u][c].pb({v,c,p}); g[v][c].pb({u,c,p}); } for(int i = 1; i <= n;i++){ for(auto j : adj[i]) d[i][j.c] = inf; d[i][0] = inf; } d[1][0] = 0; priority_queue<ngu, vector<ngu>, cmp>q; q.push({1, d[1][0], 0}); while(q.size()){ ll u = q.top().u, cost = q.top().c, col = q.top().col; q.pop(); if(cost != d[u][col]) continue; if(col == 0){ for(auto x : adj[u]){ ll v = x.v, c = x.c, p = x.p; if(col == 0){ // di nhu bthg if(d[v][0] > d[u][0] + min(p, mp[u][c] - p)){ d[v][0] = d[u][0] + min(p, mp[u][c] - p); q.push({v, d[v][0], 0}); } // thay mau canh if(d[v][c] > d[u][0]){ d[v][c] = d[u][0]; q.push({v, d[v][c], c}); } } } } else{ for(auto x : g[u][col]){ ll v = x.v, c = x.c, p = x.p; if(d[u][col] + mp[u][col] - p < d[v][0]){ d[v][0] = d[u][col] + mp[u][col] - p; q.push({v, d[v][0], 0}); } } } } cout << (d[n][0] == inf ? -1 : d[n][0]) << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }

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

Main.cpp: In function 'void to_thic_cau()':
Main.cpp:32:20: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   32 |         adj[u].pb({v,c,p}); adj[v].pb({u,c,p});
      |                    ^
Main.cpp:32:22: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   32 |         adj[u].pb({v,c,p}); adj[v].pb({u,c,p});
      |                      ^
Main.cpp:32:40: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
   32 |         adj[u].pb({v,c,p}); adj[v].pb({u,c,p});
      |                                        ^
Main.cpp:32:42: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   32 |         adj[u].pb({v,c,p}); adj[v].pb({u,c,p});
      |                                          ^
Main.cpp:33:21: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   33 |         g[u][c].pb({v,c,p}); g[v][c].pb({u,c,p});
      |                     ^
Main.cpp:33:23: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   33 |         g[u][c].pb({v,c,p}); g[v][c].pb({u,c,p});
      |                       ^
Main.cpp:33:42: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
   33 |         g[u][c].pb({v,c,p}); g[v][c].pb({u,c,p});
      |                                          ^
Main.cpp:33:44: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   33 |         g[u][c].pb({v,c,p}); g[v][c].pb({u,c,p});
      |                                            ^
Main.cpp:41:27: warning: narrowing conversion of 'd[1].std::map<int, long long int>::operator[](0)' from 'std::map<int, long long int>::mapped_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   41 |     q.push({1, d[1][0], 0});
      |                           ^
Main.cpp:52:33: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   52 |                         q.push({v, d[v][0], 0});
      |                                 ^
Main.cpp:52:47: warning: narrowing conversion of 'd[v].std::map<int, long long int>::operator[](0)' from 'std::map<int, long long int>::mapped_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   52 |                         q.push({v, d[v][0], 0});
      |                                               ^
Main.cpp:57:33: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   57 |                         q.push({v, d[v][c], c});
      |                                 ^
Main.cpp:57:47: warning: narrowing conversion of 'd[v].std::map<int, long long int>::operator[](((std::map<int, long long int>::key_type)c))' from 'std::map<int, long long int>::mapped_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   57 |                         q.push({v, d[v][c], c});
      |                                               ^
Main.cpp:67:29: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   67 |                     q.push({v, d[v][0], 0});
      |                             ^
Main.cpp:67:43: warning: narrowing conversion of 'd[v].std::map<int, long long int>::operator[](0)' from 'std::map<int, long long int>::mapped_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   67 |                     q.push({v, d[v][0], 0});
      |                                           ^
Main.cpp:64:29: warning: unused variable 'c' [-Wunused-variable]
   64 |                 ll v = x.v, c = x.c, p = x.p;
      |                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...