Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector <vector<long long>> cringe(int n, vector <vector <int>>& graph, vector <vector <long long>>& price, int start_point, long long price_now, int point_now){
- graph.resize(n, vector<int> (n));
- price.resize (n, vector <long long> (n, -1));
- for (int i=0; i<n; i++){
- if (i!=point_now){
- if (graph[point_now][i]!=0 && (price[start_point][i]==-1 || price[start_point][i]>graph[point_now][i]+price_now)){
- price[start_point][i]=graph[point_now][i]+price_now;
- long long l=price_now;
- int k=point_now;
- price_now+=graph[point_now][i];
- point_now=i;
- cringe(n, graph, price, start_point, price_now, point_now);
- price_now=l;
- point_now=k;
- }
- }
- }
- return price;
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n, z, t;
- cin>>n>>z>>t;
- vector <vector <int>> graph(n, vector <int> (n));
- vector <vector <long long>> price(n, vector <long long> (n, -1));
- vector <pair<int, int>> requests(t);
- for (int i=0; i<z; i++){
- int d, e, f;
- cin>>d>>e>>f;
- graph[d-1][e-1]=f;
- }
- for (int i=0; i<t; i++){
- cin>>requests[i].first>>requests[i].second;
- requests[i].first--;
- requests[i].second--;
- }
- int start_point;
- int point_now;
- long long price_now;
- for (int i=0; i<n; i++){
- start_point=i;
- point_now=i;
- price_now=0;
- cringe(n, graph, price, start_point, price_now, point_now);
- }
- for (int i=0; i<t; i++){
- if (requests[i].first==requests[i].second){
- cout<<0<<"\n";
- }else{
- cout<<price[requests[i].first][requests[i].second]<<"\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement