fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 18.04.2026 03:56:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define ti tuple<int, int, int>
  16. #define fi first
  17. #define se second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define eb emplace_back
  21. #define pb push_back
  22. #define TASK " "
  23.  
  24. #define ms(a, x) memset(a, x, sizeof(a))
  25. #define all(a) a.begin(), a.end()
  26. #define All(a, n) a + 1, a + 1 + n
  27.  
  28. #define LOG 19
  29.  
  30. const int INF = 1e18;
  31. const int N = 1e3 + 5;
  32. const int maxn = 100 + 5;
  33. const int mod = 1e9 + 7;
  34.  
  35.  
  36. struct node{
  37. 	int kc, u, st;
  38. 	bool operator<(const node& other) const {
  39.         return kc > other.kc; 
  40.     }
  41. };
  42. struct edge{
  43. 	int v, w, h;
  44. };
  45. int t, n, m;
  46. int a[N];
  47. // vector<int> d(N, INF);
  48. void nhap(){
  49.     cin >> t;
  50.  
  51. }
  52. vector<pi> adj[N];
  53. void dijkstra(int s){
  54. 	vector<vector<int>> d(N, vector<int>(N, INF));
  55. 	priority_queue<node> q;
  56.     d[s][1] = 0;
  57.     q.push({d[s][1], s, 1});
  58.     while(!q.empty()){
  59.         node Top = q.top(); q.pop();
  60.         int kc = Top.kc;
  61.         int u = Top.u;
  62.         int st = Top.st;
  63.         if(kc > d[u][st]) continue;
  64. 		for(auto [v, w] : adj[u]){
  65. 			// tiếp tục dùng loại xe trước đó
  66. 			if(d[v][st] > d[u][st] + w * a[st]){
  67. 				d[v][st] = d[u][st] + a[st] * w;
  68. 				q.push({d[v][st], v, st});
  69. 			}
  70. 			// mua xe mới
  71. 			if(d[v][v] > d[u][st] + w * a[st]){
  72. 				d[v][v] = d[u][st] + a[st] * w;
  73. 				q.push({d[v][v], v, v});
  74. 			}
  75.  
  76. 		}
  77.  
  78.     }
  79.     int ans = INF;
  80.     for(int i = 1; i <= n; i++){
  81. 		ans = min(ans, d[n][i]);
  82. 	}		
  83. 	cout << ans << nn;	
  84. }
  85. void solve(){
  86. 	while(t--){
  87. 		cin >> n >> m;
  88. 		for(int i = 1; i <= m; i++){
  89. 			int x, y, w;
  90. 			cin >> x >> y >> w;
  91. 			adj[x].eb(y, w);
  92. 			adj[y].eb(x, w);
  93. 		}
  94. 		for(int i = 1; i <= n; i++){
  95. 			cin >> a[i];
  96. 		}
  97. 		dijkstra(1);
  98. 		for(int i = 1; i <= n; i++) adj[i].clear();
  99. 	}
  100. }
  101. signed main(){
  102. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  103. 	nhap();
  104. 	solve();
  105. 	return 0;
  106. }
  107.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MMRGqn
language:
C++14 (gcc 8.3)
created:
7 hours 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!