fork download 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <climits>
  21. #define N 100000000
  22. using namespace std;
  23.  
  24. struct edge
  25. {
  26.   int x;
  27.   int y; 
  28.   int w;
  29. };
  30.   bool operator <(edge a,edge b)
  31.   {
  32.     return a.w<b.w;
  33.    }
  34.  
  35.  int dx[]={-1,1,0,0};
  36.  int dy[]={0,0,-1,1};
  37.  int n,m;
  38.   bool inboard(int x1,int y1)
  39.   {
  40.    if(x1>=0 && x1<n && y1>=0 && y1<m)
  41.         return true; 
  42.     else
  43.      return false; 
  44.   }
  45.  
  46. int dist[105][105];
  47. int ar[105][105];
  48. int dijkstra(int aa,int bb)
  49. {
  50.    for(int i=0;i<n;i++)
  51.     {
  52.       for(int j=0;j<m;j++)
  53.      {
  54.  
  55.        dist[i][j]=INT_MAX;
  56.      }
  57.     }
  58.    priority_queue< edge > myqueue; 
  59.    myqueue.push((edge) {0,0,0});
  60.    dist[0][0]=0;
  61.    bool fi=false;
  62.    while(!myqueue.empty()) 
  63.    {
  64.       edge curr=myqueue.top();
  65.  
  66.       myqueue.pop();
  67.       for(int i=0;i<4;i++)
  68.      {
  69.  
  70.          int xx=curr.x+dx[i];
  71.          int yy=curr.y+dy[i];  
  72.         if(inboard(xx,yy))
  73.              {
  74.                  if(dist[curr.x][curr.y] + ar[curr.x][curr.y] <dist[xx][yy])
  75.                        {
  76.  
  77.                           dist[xx][yy]=dist[curr.x][curr.y] + ar[curr.x][curr.y];
  78.  
  79.                          myqueue.push((edge) {xx,yy,dist[xx][yy]});
  80.                        }  
  81.              }
  82.      }
  83.  
  84.  
  85.    }
  86.    return dist[aa-1][bb-1];
  87. }
  88. int main()
  89. {
  90. 	 ios_base::sync_with_stdio(0);
  91.    int t;
  92.    cin >> t;
  93.    while(t-->0)
  94.   {
  95.     cin >> n >> m;
  96.  
  97.     for(int i=0;i<n;i++)
  98.      {
  99.        for(int j=0;j<m;j++)
  100.         {
  101.           cin >> ar[i][j];   
  102.         }
  103.     }
  104.       int a1,b1,T;
  105.     cin >> a1 >> b1 >> T;
  106.  
  107.     int ans=dijkstra(a1,b1);
  108.     ans=ans+ar[a1-1][b1-1];
  109.    if(ans<=T)
  110.    {
  111.     cout << "YES" << endl;
  112.     cout << (T-ans) << endl;
  113.    }
  114.    else
  115.     cout << "NO" << endl;
  116. }
  117. }
Success #stdin #stdout 0s 3564KB
comments (?)
stdin 
2
4 3 
2 3 2
2 5 1
5 3 1
3 1 1
4 2 15
2 2
1 2
1 1
2 2 2
stdout 
YES
4
NO
https://ideone.com/vGRMgi
language:
C++ (gcc 8.3)
created:
12 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!