fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. struct Edge {
  6.     ll to, cost;
  7.     Edge(ll t, ll c) : to(t), cost(c) {}
  8. };
  9. struct Elem {
  10.     ll dist, speed, cur;
  11.     Elem(ll a, ll b, ll c) : dist(a), speed(b), cur(c) {}
  12. };
  13. bool operator>(const Elem& a, const Elem& b) {
  14.     return a.dist != b.dist ? a.dist > b.dist : a.speed > b.speed;
  15. }
  16.  
  17. typedef vector< vector<Edge> > Graph;
  18. ll const INF = 1LL << 60;
  19.  
  20. int main() {
  21.     ll dist[510][60][2];
  22.     ll ans = INF;
  23.     for(int i=0; i<510; i++)
  24.         for(int j=0; j<60; j++)
  25.             for(int k=0; k<2; k++)
  26.                 dist[i][j][k] = INF;
  27.  
  28.     int n, m; cin >> n >> m;
  29.     Graph G(n);
  30.     for(int i=0; i<m; i++) {
  31.         ll a, b, t; cin >> a >> b >> t;
  32.         a--; b--;
  33.         G[a].push_back(Edge(b,t));
  34.         G[b].push_back(Edge(a,t));
  35.     }
  36.     ll v, a, b, c;
  37.     cin >> v >> a >> b >> c;
  38.     priority_queue< Elem, vector<Elem>, greater<Elem> > q;
  39.  
  40.     ll cur = 0, speed = v;
  41.     dist[0][v][0] = 0;
  42.     q.push(Elem(0, speed, cur));
  43.     while(!q.empty()) {
  44.         Elem temp = q.top(); q.pop();
  45.         cur = temp.cur, speed = temp.speed;
  46.         ll nsp = (a * speed + b) % c;
  47.         for(size_t i=0; i<G[cur].size(); i++) {
  48.             Edge e = G[cur][i];
  49.             ll d1 = dist[cur][speed][0] + e.cost * speed;
  50.             ll d2 = dist[cur][speed][1] + e.cost * speed;
  51.             // home to university
  52.             if(dist[e.to][nsp][0] > d1) {
  53.                 dist[e.to][nsp][0] = d1;
  54.                 if(e.to == n-1) dist[e.to][nsp][1] = dist[e.to][nsp][0];
  55.                 q.push(Elem(d1, nsp, e.to));
  56.             }
  57.             // university to home
  58.             if(dist[e.to][nsp][1] > d2) {
  59.                 dist[e.to][nsp][1] = d2;
  60.                 q.push(Elem(d2, nsp, e.to));
  61.             }
  62.         }
  63.     }
  64.  
  65.     for(int i=0; i<c; i++) ans = min(ans, dist[0][i][1]);
  66.     cout << ans << endl;
  67.     return 0;
  68. }
Success #stdin #stdout 0s 16416KB
comments (?)
stdin
copy 
4 4
1 2 3
2 3 1
2 4 5
3 4 2
5
4 5 6
stdout
copy 
34
https://ideone.com/Zuz1Fi
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!