This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |