Advertisement
Guest User

Untitled

a guest
Jul 5th, 2016
5,793
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define add push_back
  4. #define INF 1000000000
  5. typedef pair<int,int> ii;
  6.  
  7. vector<ii> adj[10];
  8. int dist[10][55], cost[10];
  9. int N, M, C, A, B, W;
  10.  
  11. struct State
  12. {
  13.     int v, c, d;
  14.     State() {}
  15.     State(int a, int b, int _c) { v = a; c = b; d = _c; }
  16.     bool operator>(const State &s) const { return d > s.d; }
  17. };
  18.  
  19. int dijkstra()
  20. {
  21.     for (int i = 0; i < N; i++) for (int j = 0; j <= C; j++) dist[i][j] = INF;
  22.     priority_queue< State,vector<State>,greater<State> > pq;
  23.     pq.push(State(0,C,0));
  24.     while (!pq.empty())
  25.     {
  26.         State s = pq.top(); pq.pop();
  27.         if (dist[s.v][s.c] < s.d) continue;
  28.         dist[s.v][s.c] = s.d;
  29.         for (auto p : adj[s.v])
  30.         {
  31.             int v = p.first, w = p.second;
  32.             for (int i = C-s.c; i >= 0 && s.c+i-w >= 0; i--)
  33.                 if (dist[v][s.c+i-w] > s.d+i*cost[s.v])
  34.                 {
  35.                     dist[v][s.c+i-w] = s.d+i*cost[s.v];
  36.                     pq.push(State(v,s.c+i-w,s.d+i*cost[s.v]));
  37.                 }
  38.         }
  39.     }
  40.  
  41.     int ret = INF;
  42.     for (int i = 0; i <= C; i++) ret = min(ret, dist[N-1][i]);
  43.     return ret;
  44. }
  45. int main()
  46. {
  47.     ios_base::sync_with_stdio(false);
  48.     while (scanf("%d %d %d", &N, &M, &C) && N)
  49.     {
  50.         for (int i = 0; i < N; i++) adj[i].clear();
  51.         for (int i = 0; i < M; i++)
  52.         {
  53.             scanf("%d %d %d", &A, &B, &W); A--; B--;
  54.             adj[A].add(ii(B,W));
  55.             adj[B].add(ii(A,W));
  56.         }
  57.         for (int i = 0; i < N; i++) scanf("%d", cost+i);
  58.         int ret = dijkstra();
  59.         printf("%d\n", ret==INF?-1:ret);
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement