fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define up upper_bound
  7. #define vll vector<ll>
  8. #define G vector<vll >
  9. #define gg vector<int>
  10. #define F first
  11. #define S second
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define RFOR(i,a,b) for(int i=a;i>=b;i--)
  15. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  16. #define endl '\n'
  17. #define clr(a) memset(a,0,sizeof(a))
  18. #define all(x) x.begin(),x.end()
  19. #define rll read_ll();
  20. #define gc getchar
  21. #define pc putchar
  22. typedef long long ll;
  23. template<class T> inline T lcm(T a,T b){
  24.         return a/gcd(a,b)*b;
  25. }
  26. template<typename T>
  27. void debug(T first) {
  28.     cout << first << "\n";
  29. }
  30. template<typename T, typename... Args>
  31. void debug(T first, Args... args) {
  32.     cout << first << " ";
  33.     debug(args...);
  34. }
  35.  
  36.  
  37. ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}
  38.  
  39. struct node {
  40. 	ll u,start, end,eno;
  41. 	node(ll uu, ll st, ll en, ll no):u(uu), start(st), end(en), eno(no){}
  42. };
  43.  
  44. const ll INF = 1e18;
  45. class graph {
  46. 	public : 
  47. 		ll n,e,s,t,cnt;
  48. 		// priority_queue<ll,vector<ll>,less<ll>>p;
  49. 		priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > pq;
  50. 		vector<vector<node> >adj;
  51. 		vector<ll>dist;
  52. 		vector<bool>visited;
  53. 		graph(int nodes, int edges) {
  54. 			n = nodes, e = edges;
  55. 			adj.resize(n+1);
  56. 			dist.resize(n+1);
  57. 			visited.resize(e+1);
  58. 			fill(all(visited),false);
  59. 			fill(all(dist),INF);
  60. 			s = 1, t = n;
  61. 			cnt = 0;
  62. 		}
  63. 		void addEdge(int u, int v, int start, int end) {
  64. 			adj[u].pb(node(v,start,end,cnt++));
  65. 		}
  66. 		void bfs() {
  67. 			pq.push({0,{0,1}});
  68. 			while(!pq.empty()) {
  69. 				auto current = pq.top(); pq.pop();
  70. 				ll f = current.F;
  71. 				ll currentTime = current.S.F;
  72. 				ll u = current.S.S;
  73. 				if(u == n) break;
  74. 				// if you add visited, answer will not be minium since cycles wont be allowed
  75. 				for(auto node : adj[u]) {
  76. 					ll v = node.u, start = node.start, end = node.end;
  77. 					ll eno = node.eno;
  78.  
  79.  
  80. 					if(currentTime > start) continue;
  81. 					ll currentFrustration = f + (currentTime-start)*(currentTime-start);
  82. 					if(dist[v] > currentFrustration) {
  83. 						dist[v] = currentFrustration;
  84. 					}
  85. 					// debug("visit",u,"->",v,":",eno,dist[v]);
  86. 					pq.push({currentFrustration,{end,v}});
  87. 				}
  88. 			}
  89. 		}
  90. };
  91.  
  92. int main()
  93. {
  94. 	int n, e; cin>>n>>e;
  95. 	graph g(n,e);
  96. 	for(int i = 0; i < e; i++) {
  97. 		int u, v, st, en;
  98. 		cin>>u>>v>>st>>en;
  99. 		g.addEdge(u, v, st, en);
  100. 	}
  101. 	g.bfs();
  102. 	cout<<g.dist[n]<<endl;
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 8
1 2 1 10
2 4 11 16
2 1 9 12
3 5 28 100
1 2 3 8
4 3 20 21
1 3 13 27
3 5 23 24
stdout
copy 
12
https://ideone.com/0JJGFH
language:
C++14 (gcc 8.3)
created:
5 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!