求调,floyd爆搜,模仿了题解某dalao的思路,但re了
查看原帖
求调,floyd爆搜,模仿了题解某dalao的思路,但re了
1076681
chenyuran1楼主2024/10/28 21:39

求调啊啊啊,写破防了快

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000000000;
int vil[250][250],dis[250][250],t[250];
int main(){
    ios::sync_with_stdio(0);
    int m,n;
    cin>>n>>m;//n¸ö¶¥µãmÌõ±ß
    for(int i = 0; i <= n-1; i++){
        for(int j = 0; j <= n-1; j++){
            if(i != j){
                vil[i][j] = vil[j][i] = maxn;
            }
        }
    }
    for(int i = 0; i <= n-1; i++){
        cin>>t[i];
    }
    for(int i = 0; i <= m-1; i++){
        int x,y,z;
        cin>>x>>y>>z;
        vil[x][y] = z;
        vil[y][x] = z;
    }
    int q;
    cin>>q;
    while(q--){
        int u,v,time;
        int pos = 0;
        cin>>u>>v>>time;
        int temp = pos;
        while(time >= t[pos])pos++; pos--;
        if(temp == pos){
            if(dis[u][v] == maxn){
                cout<<"-1"<<endl;
            }
            else{
                cout<<dis[u][v]<<endl;
            }
            continue;
        }
        for(int i = 0; i <= pos; i++){
            for(int j = 0; j <= pos; j++){
                dis[i][j] = dis[j][i] = vil[i][j];
            }
        }
        for(int k = 0;k <= pos; k++){
            for(int i = 0;i <= pos; i++){
                for(int j = 0;j <= pos; j++){
                    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
        if(dis[u][v] == maxn){
            cout<<"-1"<<endl;
        }
        else{
            cout<<dis[u][v]<<endl;
        }
    }

    return 0;
}

/*
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4
...................................
-1
-1
5
4
*/

2024/10/28 21:39
加载中...