fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<string> vs;
  4. typedef vector<int> vi;
  5. typedef vector<long long> vll;
  6. typedef vector<vector<int> > vvi;
  7. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
  8. #define DEC(i,a,b) for(int i=(a); i>=b; --i)
  9. #define FORV(v,i) for( int i=0;i<(int)v.size();++i)
  10. #define FORD(v,i) for(int i=v.size()-1;i>=0;--i)
  11. #define all(c) (c).begin(),(c).end()
  12. #define sz(c) int((c).size())
  13. #define pb push_back
  14. #define ull unsigned long long
  15. #define ll long long
  16. #define MOD 1000000007ULL
  17.  
  18.  
  19. typedef vector<vector<pair<int,int> > > Graph;
  20. class Comparator
  21. {
  22. 	public:
  23.  	int operator() ( const pair<int,int>& p1, const pair<int,int> &p2)
  24.  	{
  25.  		return p1.second>p2.second;
  26.  	}
  27. };
  28.  
  29.  
  30. void dijkstra(const Graph &G,const int &S,vector<int> &d)
  31. {
  32. 	d.resize(G.size(),INT_MAX);
  33. 	priority_queue<pair<int,int>, vector<pair<int,int> >, Comparator> Q;
  34. 	d[S] = 0;
  35. 	Q.push(make_pair(S,d[S]));
  36. 	while(!Q.empty())
  37. 	{
  38. 		int u = Q.top().first;
  39. 		Q.pop();
  40. 		for(unsigned int i=0; i < G[u].size(); i++)
  41. 		{
  42. 			int v = G[u][i].first;
  43. 			int w = G[u][i].second;
  44. 			if(d[v] > d[u]+w)
  45. 			{
  46. 	   			d[v] = d[u]+w;
  47. 	   			Q.push(make_pair(v,d[v]));
  48. 	  		}
  49. 	 	}
  50. 	}
  51. }
  52.  
  53. int main()
  54. {
  55. 	int t;
  56. 	ios_base::sync_with_stdio(false);
  57. 	cin>>t;
  58. 	stringstream ss;
  59. 	FOR(i,0,t)
  60. 	{
  61. 		int n,m;
  62. 		cin>>n>>m;
  63. 		Graph V(n);
  64. 		FOR(j,0,m)
  65. 		{
  66. 			int x,y,w;
  67. 			cin>>x>>y>>w;
  68. 			x--;
  69. 			y--;
  70. 			V[x].push_back(make_pair(y,w));
  71. 			V[y].push_back(make_pair(x,w));
  72. 		}
  73. 		int S;
  74. 		cin>>S;
  75. 		S--;
  76. 		vector<int> d;
  77. 		dijkstra(V,S,d);
  78. 		FORV(d,j)
  79. 		{
  80. 			if(j!=S)
  81. 			{
  82. 				if(d[j] == INT_MAX)
  83. 					ss<<-1<<" ";
  84. 				else
  85. 					ss<<d[j]<<" ";
  86. 			}
  87. 		}
  88. 		ss<<"\n";
  89. 	}
  90. 	cout<<ss.str();
  91. 	return 0;
  92. }
  93.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EszDT8
language:
C++14 (gcc 8.3)
created:
7 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!