Untitled
unknown
c_cpp
2 years ago
2.5 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 62; const ll inf = 1e9; #define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) #define pb(x) push_back(x) #define all(x) sort(x.begin() , x.end()) void dbg(){ cerr << endl; } template<typename H, typename... T> void dbg(H h, T... t){ cerr << h << ", "; dbg(t...); } #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__) int dp[maxn][maxn][maxn] , pd[maxn][maxn] , dis[maxn][maxn][maxn]; int n, m , r; vector<int> vec; void print(){ for(int i = 0 ; i < r ; i++){ int u , v , cr; cin >> u >> v >> cr; --u;--v;--cr; cr = min(cr , 60); vec.push_back(dp[u][v][cr]); } for(auto e : vec) cout << e << '\n'; } void update(){ for(int cr = 1 ; cr < maxn ; cr++){ for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ for(int x = 0 ; x < n ; x++){ dp[i][j][cr] = min(dp[i][x][cr-1] + pd[x][j] , dp[i][j][cr]); //er(dp[i][x][k-1] + pd[x][j] , dp[i][j][k]); } } } } } void nec(){ //dp[i][j][k] = says that if i is the start vertex and j is the finish vertex in max k changes for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) for(int k = 0 ; k < maxn ; k++) dp[i][j][k] = inf; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ pd[i][j] = dis[i][j][0]; for(int cr = 0 ; cr < m ; cr++){ pd[i][j] = min(dis[i][j][cr] , pd[i][j]); } } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ dp[i][j][0] = pd[i][j]; } } update(); } void floyd(){ for(int cr = 0 ; cr < m ; cr++){ for(int k = 0 ; k < n ; k++){ for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if(dis[i][j][cr] > dis[i][k][cr] + dis[k][j][cr]){ dis[i][j][cr] = dis[i][k][cr] + dis[k][j][cr]; } } } } } nec(); } void read_input1(){ cin >> n >> m >> r; for(int cr = 0 ; cr < m ; cr++) for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) dis[i][j][cr] = inf; //dis[first vertex][sec vertex][ which car that is!] for(int cr = 0 ; cr < m ; cr++){ for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ cin >> dis[i][j][cr]; } } } floyd(); } int main(){ ios; read_input1(); print(); return 0; }
Editor is loading...