fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define endl '\n'
  3. #define INF 1000000000
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<int,int> pii;
  7. int n,m;
  8. int g0[110][110];
  9. vector<int> g[110];
  10. int dijkstra(int s,int t)
  11. {
  12. 	priority_queue<pii,vector<pii>,greater<pii>> q;
  13. 	q.push(make_pair(0,s));
  14. 	int dis[110];
  15. 	for(int i=1;i<=n;i++)
  16. 		dis[i]=INF;
  17. 	dis[s]=0;
  18. 	while(!q.empty())
  19. 	{
  20. 		int i=q.top().second;
  21. 		if(q.top().first>dis[i])
  22. 		{ q.pop(); continue; }
  23. 		q.pop();
  24. 		if(i==t)return dis[i];
  25.         for(int j:g[i])
  26.             if(!(i==s&&j==t || i==t&&j==s) && dis[i]+g0[i][j]<dis[j])
  27. 			{
  28. 				dis[j]=dis[i]+g0[i][j];
  29. 				q.push(make_pair(dis[i]+g0[i][j],j));
  30. 			}
  31. 		dis[i]=0;
  32. 	}
  33. 	return INF;
  34. }
  35. int main()
  36. {
  37. 	ios::sync_with_stdio(0);
  38. 	cin.tie(0);
  39.  
  40. 	//input
  41. 	cin>>n>>m;
  42. 	for(int i=1;i<=n;i++)
  43. 		for(int j=1;j<=n;j++)
  44. 			g0[i][j]=INF;
  45. 	for(int i=0;i<m;i++)
  46. 	{
  47. 		int a,b,c;
  48. 		cin>>a>>b>>c;
  49. 		if(g0[a][b]==INF)
  50. 		{
  51. 			g[a].push_back(b);
  52. 			g[b].push_back(a);
  53. 		}
  54. 		g0[a][b]=g0[b][a]=min(g0[a][b],c);
  55. 	}
  56.  
  57.     //solve
  58.     int ans=INF;
  59.     for(int i=1;i<=n;i++)
  60. 		for(int j=i+1;j<=n;j++)
  61. 			ans=min(ans,dijkstra(i,j)+g0[i][j]);
  62. 	if(ans!=INF) cout<<ans<<endl;
  63. 	else cout<<"No solution."<<endl;
  64. }
  65.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
stdout
copy 
61
https://ideone.com/HcKeWJ
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!