Submission #477383

#TimeUsernameProblemLanguageResultExecution timeMemory
477383Qw3rTyRobot (JOI21_ho_t4)C++11
0 / 100
1 ms1104 KiB
#include <bits/stdc++.h> #define int long long #define INF 1e16 #define pi pair<int,int> #define fi first #define se second #define pb push_back using namespace std; const int maxN = 2e3+5; struct cmp{ bool operator() (pi a, pi b){ return a.fi > b.fi; } }; struct edge{ int to,col,p; edge(){}; edge(int to, int col, int p){ this -> to = to; this -> col = col; this -> p = p; } }; vector<edge> adj[maxN]; vector<pi> adj2[maxN]; int N,M; int dist[maxN]; bool vis[maxN]; int f[maxN][maxN]; //f[i][j] = # of roads with color j at node i signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); //freopen("../test.in","r",stdin); cin >> N >> M; for(int i = 1; i <= M; ++i){ int a,b,c,p; cin >> a >> b >> c >> p; adj[a].pb(edge(b,c,p)); adj[b].pb(edge(a,c,p)); ++f[a][c]; ++f[b][c]; } //construct adj2 for(int i = 1; i <= N; ++i){ int MIN = INF; //MIN = min (roads with color j at node i) for 1 <= j <= M for(int j = 1; j <= M; ++j){ MIN = min(MIN,f[i][j]); } for(edge e: adj[i]){ adj2[i].pb(pi(e.to,min(MIN+1,f[i][e.col]-1)*e.p)); } } //dijk for(int i = 1; i <= N; ++i)dist[i] = INF; memset(vis,false,sizeof(vis)); priority_queue<pi,vector<pi>,cmp> Q; Q.push(pi(0,1)); dist[1] = 0; while(!Q.empty()){ pi p = Q.top(); Q.pop(); int loc = p.se; if(vis[loc])continue; vis[loc] = true; for(auto x: adj2[loc]){ if(dist[loc] + x.se < dist[x.fi]){ dist[x.fi] = dist[loc] + x.se; if(!vis[x.fi]){ Q.push(pi(dist[x.fi],x.fi)); } } } } if(dist[N] == INF)cout << -1 << '\n'; else cout << dist[N] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...