fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int tc;
  9.  
  10.  
  11. #define pp pair<int,int>
  12. using namespace std;
  13. struct pri
  14. {
  15.     int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
  16.     {
  17.         return p1.second<p2.second;
  18.     }
  19. }p;
  20.  
  21. int main() {
  22.     //freopen("test.inp", "r", stdin);
  23.     scanf("%d", &tc);
  24.     while (tc --) {
  25.         int n, m;
  26.         priority_queue<pp,vector<pp>,pri> q;
  27.         cin>>n >> m;
  28.         vector<pp> g[n+1];
  29.         int u,v,w;
  30.         for(int i=0;i<m;i++)
  31.         {
  32.             cin>>u>>v>>w;
  33.             g[u].push_back(pp(v,w));
  34.             g[v].push_back(pp(u,w));
  35.         }
  36.         int s = 1;
  37.         int d[n+1];
  38.         for(int i=1;i<=n;i++)
  39.             d[i]=999999;
  40.         d[s]=0;
  41.         q.push(pp(s,d[s]));
  42.         while(!q.empty())
  43.         {
  44.             u=q.top().first;
  45.             q.pop();
  46.             int size=g[u].size();
  47.             for(int i=0;i<size;i++)
  48.             {
  49.                 v=g[u][i].first;
  50.                 w=g[u][i].second;
  51.                 if(d[v]>d[u]+w)
  52.                 {
  53.                     d[v]=d[u]+w;
  54.                     q.push(pp(v,d[v]));
  55.                 }
  56.             }
  57.         }
  58.         int rs = 0;
  59.         for(int i=1;i<=n;i++) {
  60.             rs = max(rs, d[i] - d[i - 1]);
  61.         }
  62.         printf("%d\n", rs);
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uwgIxL
language:
C++ (gcc 8.3)
created:
8 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!