제출 #413000

#제출 시각아이디문제언어결과실행 시간메모리
413000ChaskaRobot (JOI21_ho_t4)C++11
0 / 100
609 ms56376 KiB
#include <bits/stdc++.h> #define pb push_back #define sp " " #define sl "\n" #define fi first #define se second #define mp make_pair #define sz(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define rev(a) reverse(a.begin(),a.end()) #define PI 3.141592 #define fo(i,n) for (int i=0;i<n;i++) #define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) using namespace std; typedef long long ll; typedef pair<ll,ll> ii; typedef pair<int,ii> iii; typedef vector<int> vi; typedef vector<ii> vii; const int N=1e5+5,M=2e5+5,mod=1e9+7; ll n,m; map<ll,ll> h[N]; map<ll,ll> hp[N]; vector<ll> g[N]; map<ii,ll> pr; map<ii,ll> co; bool vs[N]; map<ll,vector<ll>> back[N]; ll res[N]; priority_queue<ii,vector<ii>,greater<ii>> pq; void dij(ll cost,ll node) { if (vs[node]) return; vs[node] = true; res[node] = cost; //cout << node << " "<< res[node] << "\n"; for (int u : g[node]) { int colorcito = co[{node,u}]; if (!vs[u]) if ( h[node][colorcito]==1) { pq.push({cost,u}); //dij(u,cost); ///cout << node << " " << u << "\n"; } } for (int u : g[node]) { int colorcito = co[{node,u}]; ll precioo = pr[{node,u}]; if (!vs[u]) if (h[node][colorcito]>1) { pq.push({cost+min(precioo,hp[node][colorcito]-precioo),u}); /// cout << node << " " << u << "\n"; if (precioo <= hp[node][colorcito]-precioo) { //h[node][colorcito]--; h[u][colorcito]--; hp[u][colorcito] -= precioo; //hp[node][colorcito] -= precioo; } else { for (int v : back[node][colorcito]) { h[v][colorcito]--; hp[v][colorcito] -= pr[{node,v}]; } h[u][colorcito] = 1; } //dij(u,cost); } } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(); cin >> n >> m; for (int i=0;i<m;i++) { ll a,b,c,p; cin >> a >> b >> c >> p; co[{a,b}] = c; co[{b,a}] = c; pr[{a,b}] = p; pr[{b,a}] = p; g[a].push_back(b); g[b].push_back(a); back[a][c].push_back(b); back[b][c].push_back(a); h[a][c]++; hp[a][c] += p; h[b][c]++; hp[b][c] += p; } pq.push({0,1}); while (!pq.empty()) { auto x = pq.top(); pq.pop(); dij(x.fi,x.se); } if (!vs[n]) cout << -1; else cout << res[n]; return 0; } // Recuerda limites // Recuerda casos especiales
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...