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 name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, m;
struct dl{
ll h;
int a, b;
bool operator < (const dl &o) const {return h > o.h;}
};
vector <dl> g[maxn];
ll cost[1003][2003], dp[1003][2003];
void sub1(){
set <int> luu[1003];
fi(i, 1, n){
luu[i].insert(0);
for(auto [j, cl, p]: g[i]){
cost[i][cl] += p;
luu[i].insert(cl);
}
}
fi(i, 1, n)
fi(j, 0, m) dp[i][j] = 1e18;
priority_queue <dl> q;
dp[1][0] = 0;
q.push({0, 1, 0});
while(q.size()){
auto [h, u, x] = q.top(); q.pop();
if(h != dp[u][x]) continue;
if(u == n) break;
for(auto [v, cl, p]: g[u]){
for(auto i: luu[u]){
if(cl == i){
if(dp[v][i] > h + cost[u][i] - p){
dp[v][i] = h + cost[u][i] - p;
// cout << v << " " << dp[v][i] << " " << i << endl;
q.push({dp[v][i], v, i});
}
}
else{
if(dp[v][i] > h + cost[u][i] + p){
dp[v][i] = h + cost[u][i] + p;
// cout << v << " " << dp[v][i] << " " << i << endl;
q.push({dp[v][i], v, i});
}
}
}
}
}
ll res = 1e18;
fi(i, 1, m) res = min(res, dp[n][i]);
if(res != 1e18) cout << res;
else cout << -1;
exit(0);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// freopen(name".in", "r", stdin);
// freopen(name".out", "w", stdout);
cin >> n >> m;
fi(i, 1, m){
int u, v, c, p; cin >> u >> v >> c >> p;
g[u].pb({v, c, p});
g[v].pb({u, c, p});
}
if(n <= 1000 && m <= 2000) sub1();
}
Compilation message (stderr)
Main.cpp: In function 'void sub1()':
Main.cpp:48:43: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
48 | q.push({dp[v][i], v, i});
| ^
Main.cpp:55:43: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
55 | q.push({dp[v][i], v, i});
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |