Untitled

 avatar
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...