fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. #define iii pair<int, pair<int, int> >
  3. using namespace std;
  4.  
  5. bool visited[55][1005];
  6. int dist[55][1005];
  7. int tolls[55][55];
  8. int times[55][55];
  9. int n, p;
  10.  
  11. void dijkstra() {
  12.     priority_queue<iii, vector<iii >, greater<iii > > pq;
  13.     pq.push(make_pair(0, make_pair(1, 0)));
  14.     dist[1][0]=0;
  15.     while (!pq.empty()) {
  16.         iii top=pq.top();
  17.         pq.pop();
  18.         int nd=(top.second).first;
  19.         int ndtime=(top.second).second;
  20.         visited[nd][ndtime]=1;
  21.         for (int i=1; i<=n; i++) {
  22.             int toll=tolls[nd][i];
  23.             int time=times[nd][i];
  24.             if (time+ndtime<=p && nd!=i) {
  25.                 if (!visited[i][time+ndtime]) {
  26.                     if (dist[i][time+ndtime]>dist[nd][ndtime]+toll) {
  27.                         dist[i][time+ndtime]=dist[nd][ndtime]+toll;
  28.                         pq.push(make_pair(dist[i][time+ndtime], make_pair(i, time+ndtime)));
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.     }
  34. }
  35.  
  36. main() {
  37.     while (1) {
  38.         scanf("%d %d", &n, &p);
  39.         if (n==0 && p==0) break;
  40.         for (int i=0; i<55; i++) {
  41.             for (int j=0; j<1005; j++) {
  42.                 dist[i][j]=1<<30;
  43.                 visited[i][j]=0;
  44.             }
  45.         }
  46.         for (int i=1; i<=n; i++) {
  47.             for (int j=1; j<=n; j++) scanf("%d", &times[i][j]);
  48.         }
  49.         for (int i=1; i<=n; i++) {
  50.             for (int j=1; j<=n; j++) scanf("%d", &tolls[i][j]);
  51.         }
  52.         dijkstra();
  53.         int ans=1<<30, index;
  54.         for (int i=1; i<=p; i++) {
  55.             if (ans>dist[n][i]) {
  56.                 ans=dist[n][i];
  57.                 index=i;
  58.             }
  59.         }
  60.  
  61.         printf("%d %d\n", ans, index);
  62.     }
  63. }
  64.  
Success #stdin #stdout 0s 3116KB
comments (?)
stdin
copy 
4 7
0 5 2 3
5 0 2 3
3 1 0 2
3 3 2 0

0 2 2 7
2 0 1 2
2 2 0 5
7 2 5 0

0 0
stdout
copy 
6 6
https://ideone.com/H8UUMf
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!