結果
問題 | No.2915 辺更新価値最大化 |
ユーザー |
|
提出日時 | 2024-10-04 22:12:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 11,681 bytes |
コンパイル時間 | 1,781 ms |
コンパイル使用メモリ | 191,420 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-04 22:12:45 |
合計ジャッジ時間 | 6,840 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 TLE * 1 |
コンパイルメッセージ
main.cpp: In static member function 'static std::vector<_Tp> shortest_path::dijkstra(graph<T>&, int)': main.cpp:213:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 213 | auto [d, v] = que.top(); | ^ main.cpp: In static member function 'static std::vector<std::vector<std::pair<int, T> > > shortest_path::pered(graph<T>&, int)': main.cpp:282:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 282 | auto [d, v, s] = que.top(); | ^ main.cpp: In function 'void solve()': main.cpp:387:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 387 | auto [u, v, w] = es[i]; | ^
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define all(a) (a).begin(), (a).end()#define pb push_back#define fi first#define se secondmt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());const ll MOD1000000007 = 1000000007;const ll MOD998244353 = 998244353;const ll MOD[3] = {999727999, 1070777777, 1000000007};const ll LINF = 1LL << 60LL;const int IINF = (1 << 30) - 2;template<typename T>struct edge{int from;int to;T cost;int id;edge(){}edge(int to, T cost=1) : from(-1), to(to), cost(cost){}edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}void reverse(){swap(from, to);}};template<typename T>struct edges : std::vector<edge<T>>{void sort(){std::sort((*this).begin(),(*this).end(),[](const edge<T>& a, const edge<T>& b){return a.cost < b.cost;});}};template<typename T = bool>struct graph : std::vector<edges<T>>{private:int n = 0;int m = 0;edges<T> es;bool dir;public:graph(int n, bool dir) : n(n), dir(dir){(*this).resize(n);}void add_edge(int from, int to, T cost=1){if(dir){es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m++));}else{if(from > to) swap(from, to);es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m));(*this)[to].push_back(edge<T>(to, from, cost, m++));}}int get_vnum(){return n;}int get_enum(){return m;}bool get_dir(){return dir;}edge<T> get_edge(int i){return es[i];}edges<T> get_edge_set(){return es;}};template<typename T>struct redge{int from, to;T cap, cost;int rev;redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}};template<typename T> using Edges = vector<edge<T>>;template<typename T> using weighted_graph = vector<Edges<T>>;template<typename T> using tree = vector<Edges<T>>;using unweighted_graph = vector<vector<int>>;template<typename T> using residual_graph = vector<vector<redge<T>>>;class shortest_path{public:template<typename T>static vector<T> bfs(graph<T> &G, int s){int n = G.get_vnum();vector<T> dist(n, -1);dist[s] = 0;queue<int> que;que.push(s);while(!que.empty()){int v = que.front();que.pop();for(auto e : G[v]) if(dist[e.to]==-1){dist[e.to] = dist[v] + 1;que.push(e.to);}}return dist;}template<typename T>static vector<T> binary_bfs(graph<T> &G, int s){int n = G.get_vnum();vector<T> dist(n, -1);dist[s] = 0;deque<int> deq;deq.push_front(s);while(!deq.empty()){int v = deq.front();deq.pop_front();for(auto e : G[v]) if(dist[e.to]==-1){dist[e.to] = dist[v] + e.cost;if(e.cost) deq.push_back(e.to);else deq.push_front(e.to);}}return dist;}template<typename T>static vector<T> constant_bfs(graph<T> &G, int s, T W){int n = G.get_vnum();vector<T> dist(n, -1);vector<vector<int>> cand(n*W+1);dist[s] = 0;cand[0].push_back(s);for(int d=0; d<=n*W; d++) for(int v : cand[d]){if(dist[v]!=-1) continue;for(auto e : G[v]) if(dist[v] + dist[e.to] < dist[e.ot]){dist[e.to] = dist[v] + e.cost;cand[dist[e.to]].push_back(e.to);}}return dist;}template<typename T>static vector<T> complement_bfs(graph<T> &G, int s){int n = G.get_vnum();map<pair<int, int>, bool> mp;for(int v=0; v<n; v++) for(auto e : G[v]) mp[{v, e.to}] = true;vector<T> dist(n, -1);vector<int> unvisited;for(int v=0; v<n; v++) if(v != s) unvisited.push_back(v);queue<int> visited;visited.push(s);dist[s] = 0;while(!visited.empty()){int v = visited.front();visited.pop();vector<int> nxt;for(int to : unvisited){if(!mp[{v, to}]){visited.push(to);dist[to] = dist[v]+1;}else{nxt.pb(to);}}unvisited = nxt;}return dist;}template<typename T>static vector<T> dijkstra(graph<T> &G, int s){int n = G.get_vnum();const T TINF = numeric_limits<T>::max()/2;vector<T> dist(n, TINF);dist[s] = 0;priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> que;que.push({0, s});while(!que.empty()){auto [d, v] = que.top();que.pop();if(dist[v] < d) continue;for(auto e : G[v]){if(dist[v] + e.cost < dist[e.to]){dist[e.to] = dist[v] + e.cost;que.push({dist[e.to], e.to});}}}return dist;}template<typename T>static vector<T> bellmanford(graph<T> &G, int s){int n = G.get_vnum();bool dir = G.get_dir();const T TINF = numeric_limits<T>::max()/2;edges<T> es = G.get_edge_set();vector<T> dist(n, TINF);vector<bool> flag(n, false);dist[s] = 0;for(int i=0; i<n; i++) for(auto e : es){if(dist[e.from]!=TINF && dist[e.from]+e.cost<dist[e.to]) dist[e.to] = dist[e.from] + e.cost;if(!dir && dist[e.to]!=TINF && dist[e.to]+e.cost<dist[e.from]) dist[e.from] = dist[e.to] + e.cost;}for(int i=0; i<n; i++) for(auto e : es){if(dist[e.from]!=TINF && dist[e.from]+e.cost<dist[e.to]) dist[e.to] = dist[e.from] + e.cost, flag[e.to]=true;if(!dir && dist[e.to]!=TINF && dist[e.to]+e.cost<dist[e.from]) dist[e.from] = dist[e.to] + e.cost, flag[e.from]=true;}for(int i=0; i<n; i++) for(auto e : es){flag[e.to] = flag[e.to] | flag[e.from];if(!dir) flag[e.from] = flag[e.from] | flag[e.to];}for(int v=0; v<n; v++) if(flag[v]) dist[v] = -TINF;return dist;}template<typename T>static vector<vector<T>> warshall_floyd(graph<T> &G){int n = G.get_vnum();const T TINF = numeric_limits<T>::max()/2;vector<vector<T>> dist(n, vector<T>(n, TINF));for(int v=0; v<n; v++) dist[v][v] = 0;for(int v=0; v<n; v++) for(auto e : G[v]) dist[v][e.to] = min(dist[v][e.to], e.cost);for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(dist[i][k] < TINF && dist[k][j] < TINF) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);return dist;}template<typename T>static vector<vector<pair<int, T>>> pered(graph<T> &G, int k){int n = G.get_vnum();const T TINF = numeric_limits<T>::max()/2;priority_queue<tuple<T, int, int>, vector<tuple<T, int, int>>, greater<>> que;vector<vector<pair<int, T>>> neibors(n);vector<unordered_map<int, T>> mp(n);for(int v=0; v<n; v++){que.push({0, v, v});mp[v][v] = 0;}while(!que.empty()){auto [d, v, s] = que.top();que.pop();if((int)neibors[v].size()==k) continue;if(mp[v].find(s)!=mp[v].end()) if(mp[v][s] < d) continue;neibors[v].push_back({s, d});for(auto e : G[v]){if((int)neibors[e.to].size()==k) continue;if(mp[e.to].find(s)==mp[e.to].end()) mp[e.to][s] = TINF;if(d + e.cost < mp[e.to][s]){mp[e.to][s] = d + e.cost;que.push({d+e.cost, e.to, s});}}}return neibors;}// template<typename T>// static T malick_mittal_gupta(graph<T> &G, int s, int t){// // declear variable// const T TINF = numeric_limits<T>::max()/2;// dijkstra<T> dijk_s(G, s), dijk_t(G, t);// int n = G.get_vnum();// int m = G.get_enum();// vector<T> dist_s = dijk_s.get_dist();// vector<T> dist_t = dijk_t.get_dist();// vector<int> path = dijk_s.get_vpath(t);// int p = (int)path.size();// path.push_back(n); // sentinel// vector<vector<int>> ch(n);// for(int v=0; v<n; v++) if(v != s) ch[dijk_s.get_vpar(v)].push_back(v);// vector<int> label(n, -1);// function<void(int, int)> labeling = [&](int v, int l){// label[v] = l;// for(int to : ch[v]) dfs(to, l);// };// for(int i=0; i<p; i++){// label[path[i]] = i;// for(int to : ch[path[i]]) if(to != path[i+1]){// dfs(to, path[i], i);// }// }// vector<vector<int>> sevt(p), eevt(p);// for(int v=0; v<n; v++) for(auto e : G[v]) if(dijk_s.get_epar(e.to).id != e.id && label[v] < label[e.to]){// sevt[label[v]].push_back(e.id);// tevt[label[v]].push_back(e.id);// }// T ans = TINF;// for(int i=1; i<p; i++){// int u = path[i-1], v = path[i], e_id = dijk_s.get_epar(v);// // start event with label = i-1// for(int id : sevt[i-1]){// auto e = G.get_edge(id);// int x = e.from, y = e.to;// if(label[x] > label[y]) swap(x, y);// eset.insert({dist_s[x]+e.cost+dist_t[y], id});// }// // calc ans// if(!eset.empty()) ans = min(ans, (*eset.begin()).first);// // end event with label = i// for(int id : evt[i]){// auto e = G.get_edge(id);// int x = e.from, y = e.to;// if(label[x] > label[y]) swap(x, y);// eset.erase({dist_s[x]+e.cost+dist_t[y], id});// }// }// return ans;// }template<typename T>static vector<T> yen(graph<T> &G, int s, int t, int k){}};void solve(){int n, m, q; cin >> n >> m >> q;vector<tuple<int, int, ll>> es;for(int i=0; i<m; i++){int u, v; cin >> u >> v;u--; v--;ll w; cin >> w;es.pb({u, v, w});}vector<bool> check(m, true);while(q--){int j; cin >> j;check[j-1] = !check[j-1];graph<ll> G(n, true);for(int i=0; i<m; i++){auto [u, v, w] = es[i];if(check[i]) G.add_edge(u, v, -w);}auto dist = shortest_path::dijkstra<ll>(G, 0);if(dist[n-1]>LINF){cout << "NaN\n";}else{cout << -dist[n-1] << '\n';}}}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int T=1;//cin >> T;while(T--) solve();}