fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ____AnhKietSS____ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define NamDinh signed
  5. #define ii pair<int,int>
  6. #define ll long long
  7. #define foru(i,d,c) for(int i=(d);i<=(c);i++)
  8. #define ford(i,d,c) for(int i=(d);i>=(c);i--)
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define pf push_front
  13.  
  14. using namespace std;
  15.  
  16. const ll INF=4557430888798830399LL;
  17.  
  18. struct Edge
  19. {
  20.     int v;
  21.     ll w;
  22. };
  23.  
  24. int n,m,k,q;
  25. vector<vector<Edge> > a;
  26.  
  27. int id(int r,int c)
  28. {
  29.     return r*m+c;
  30. }
  31.  
  32. ll dijkstra(int s,int t)
  33. {
  34.     if(s==t)return 0;
  35.  
  36.     vector<ll> d(n*m,INF);
  37.     priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
  38.  
  39.     d[s]=0;
  40.     pq.push({0,s});
  41.  
  42.     while(!pq.empty())
  43.     {
  44.         ll du=pq.top().fi;
  45.         int u=pq.top().se;
  46.         pq.pop();
  47.  
  48.         if(du!=d[u])continue;
  49.         if(u==t)return du;
  50.  
  51.         for(int i=0;i<(int)a[u].size();i++)
  52.         {
  53.             int v=a[u][i].v;
  54.             ll w=a[u][i].w;
  55.  
  56.             if(d[v]>d[u]+w)
  57.             {
  58.                 d[v]=d[u]+w;
  59.                 pq.push({d[v],v});
  60.             }
  61.         }
  62.     }
  63.  
  64.     return -1;
  65. }
  66.  
  67. NamDinh main()
  68. {
  69.     ____AnhKietSS____
  70.  
  71.     freopen("MAZE.INP","r",stdin);
  72.     freopen("MAZE.OUT","w",stdout);
  73.  
  74.     cin>>n>>m>>k>>q;
  75.  
  76.     vector<string> s(n);
  77.     foru(i,0,n-1)cin>>s[i];
  78.  
  79.     a.resize(n*m);
  80.  
  81.     int dx[4]={-1,1,0,0};
  82.     int dy[4]={0,0,-1,1};
  83.  
  84.     foru(i,0,n-1)
  85.     {
  86.         foru(j,0,m-1)
  87.         {
  88.             if(s[i][j]=='#')continue;
  89.  
  90.             int u=id(i,j);
  91.  
  92.             foru(z,0,3)
  93.             {
  94.                 int x=i+dx[z];
  95.                 int y=j+dy[z];
  96.  
  97.                 if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.')
  98.                 {
  99.                     int v=id(x,y);
  100.                     a[u].pb({v,1});
  101.                 }
  102.             }
  103.         }
  104.     }
  105.  
  106.     foru(i,1,k)
  107.     {
  108.         int x,y,u,v;
  109.         ll w;
  110.  
  111.         cin>>x>>y>>u>>v>>w;
  112.  
  113.         --x;
  114.         --y;
  115.         --u;
  116.         --v;
  117.  
  118.         int p=id(x,y);
  119.         int t=id(u,v);
  120.  
  121.         a[p].pb({t,w});
  122.         a[t].pb({p,w});
  123.     }
  124.  
  125.     while(q--)
  126.     {
  127.         int x,y,u,v;
  128.  
  129.         cin>>x>>y>>u>>v;
  130.  
  131.         --x;
  132.         --y;
  133.         --u;
  134.         --v;
  135.  
  136.         int s1=id(x,y);
  137.         int s2=id(u,v);
  138.  
  139.         cout<<dijkstra(s1,s2)<<"\n";
  140.     }
  141.  
  142.     return 0;
  143. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bBnej0
language:
C++ (gcc 8.3)
created:
1 day 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!