結果

問題 No.3230 Mutual Corresponding System
コンテスト
ユーザー GOTKAKO
提出日時 2025-08-08 22:47:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,406 bytes
コンパイル時間 1,862 ms
コンパイル使用メモリ 211,716 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-08 22:48:05
合計ジャッジ時間 36,081 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N,M; cin >> N >> M;
    vector<int> T(N);
    for(auto &t : T) cin >> t;
    vector<vector<int>> A(N,vector<int>(N));
    for(auto &h : A) for(auto &w : h) cin >> w;

    int n = 1500;
    vector<vector<int>> day(n+1,vector<int>(N)),OK = day;
    day.at(0) = T;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> Q;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(i == k) continue;
            Q.push({T.at(i)+A.at(i).at(k),1,k});
        }
    } 
    while(Q.size()){
        auto [d,let,pos] = Q.top(); Q.pop();
        if(let == n+1) break;
        OK.at(let).at(pos)++;
        if(OK.at(let).at(pos) == N-1){
            if(day.at(let-1).at(pos) > d){
                OK.at(let).at(pos)--;
                Q.push({day.at(let-1).at(pos),let,pos}); continue;                
            }
            day.at(let).at(pos) = d;
            for(int to=0; to<N; to++) if(to != pos) Q.push({d+A.at(pos).at(to),let+1,to});
        }
    }
    for(int i=0; i<N; i++){
        if(M > n){
            long long d1 = day.at(n).at(i),d2 = day.at(n-1).at(i);
            long long more = M-n,d = d1-d2;
            cout << more*d+d1 << " ";
        }
        else cout << day.at(M).at(i) << " ";
        
    }
    cout << endl;
}
0