fork(30) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<limits>
  13. #include<climits>
  14. #include<cmath>
  15. #include<functional>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<fstream>
  19. #include<typeinfo>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long int ll;
  24. typedef short int i16;
  25. typedef unsigned long long int u64;
  26. typedef unsigned int u32;
  27. typedef unsigned short int u16;
  28. typedef unsigned char u8;
  29.  
  30. const int N = 128;
  31.  
  32. struct edge
  33. {
  34.     int to,w;
  35.     edge(){}
  36.     edge(int a, int b)
  37.     {
  38.         to=a;
  39.         w=b;
  40.     }
  41. };
  42.  
  43. struct el
  44. {
  45.     int vertex,cost;
  46.     el(){}
  47.     el(int a, int b)
  48.     {
  49.         vertex=a;
  50.         cost=b;
  51.     }
  52.     bool operator<(const el &a) const
  53.     {
  54.         return cost>a.cost;
  55.     }
  56. };
  57.  
  58. priority_queue <el> pq;
  59.  
  60. vector <edge> v[N];
  61.  
  62. vector <int> dist[N];
  63.  
  64. int n,m,q;
  65.  
  66. void input()
  67. {
  68.     int i,a,b,c;
  69.     for(i=0;i<N;i++)
  70.         v[i].clear();
  71.     for(i=1;i<=m;i++)
  72.     {
  73.         scanf("%d %d %d", &a, &b, &c);
  74.         a++;
  75.         b++;
  76.         v[a].push_back(edge(b,c));
  77.         v[b].push_back(edge(a,c));
  78.     }
  79. }
  80.  
  81. void Dijkstra(int starting_node, int ending_node)
  82. {
  83.     int i,current_distance;
  84.     el curr;
  85.     for(i=0;i<N;i++)
  86.         dist[i].clear();
  87.     while(!pq.empty())
  88.         pq.pop();
  89.     pq.push(el(starting_node,0));
  90.     while(!pq.empty())
  91.     {
  92.         curr=pq.top();
  93.         pq.pop();
  94.         if(dist[curr.vertex].size()==0)
  95.             dist[curr.vertex].push_back(curr.cost);
  96.         else if(dist[curr.vertex].back()!=curr.cost)
  97.             dist[curr.vertex].push_back(curr.cost);
  98.         if(dist[curr.vertex].size()>2)
  99.             continue;
  100.         for(i=0;i<v[curr.vertex].size();i++)
  101.         {
  102.             if(dist[v[curr.vertex][i].to].size()==2)
  103.                 continue;
  104.             current_distance=v[curr.vertex][i].w+curr.cost;
  105.             pq.push(el(v[curr.vertex][i].to,current_distance));
  106.         }
  107.     }
  108.     if(dist[ending_node].size()<2)
  109.         printf("?\n");
  110.     else
  111.         printf("%d\n", dist[ending_node][1]);
  112. }
  113.  
  114. void solve()
  115. {
  116.     int i,a,b;
  117.     scanf("%d", &q);
  118.     for(i=1;i<=q;i++)
  119.     {
  120.         scanf("%d %d", &a, &b);
  121.         a++;
  122.         b++;
  123.         Dijkstra(a,b);
  124.     }
  125. }
  126.  
  127. int main()
  128. {
  129.     int i;
  130.     for(i=1;scanf("%d %d", &n, &m)!=EOF;i++)
  131.     {
  132.         input();
  133.         printf("Set #%d\n", i);
  134.         solve();
  135.     }
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QpWFnR
language:
C++14 (gcc 8.3)
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!