#1179985 (C++23) No.3653 Space-Time Courier

• 問題: No.3653 Space-Time Courier
• ユーザー: tau1235
• 提出日時: 2026-08-28 22:22:22
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 648 ms / 4,000 ms
• コード長: 3,148 bytes
• コンパイル時間: 2,615 ms
• コンパイル使用メモリ: 354,136 KB
• 実行使用メモリ: 53,248 KB
• 最終ジャッジ日時: 2026-08-28 22:22:33
• 合計ジャッジ時間: 9,683 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 28

ソースコード

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

//https://www.geeksforgeeks.org/dsa/johnsons-algorithm/
const long long INF = 1e15; 

struct Edge {
    int to;
    int weight;
};

typedef pair<long long, int> pii;

// Dijkstra's algorithm for non-negative edge weights
vector<long long> Dijkstra(int V, const vector<vector<Edge>>& adj, int src) {
    vector<long long> dist(V, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second; // Fixed: added .top()
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    return dist;
}

// Bellman-Ford to find h[] and detect negative cycles
vector<long long> BellmanFord(int V, const vector<vector<int>>& edges, bool& hasCycle) {
    vector<long long> h(V + 1, INF);
    h[V] = 0; 

    vector<vector<int>> all_edges = edges;
    for (int i = 0; i < V; i++) all_edges.push_back({V, i, 0});

    for (int i = 0; i < V; i++) { 
        for (auto& e : all_edges) {
            if (h[e[0]] != INF && h[e[0]] + e[2] < h[e[1]]) {
                h[e[1]] = h[e[0]] + e[2];
            }
        }
    }

    hasCycle = false;
    for (auto& e : all_edges) {
        if (h[e[0]] != INF && h[e[0]] + e[2] < h[e[1]]) {
            hasCycle = true;
            return {};
        }
    }

    h.pop_back(); 
    return h;
}

vector<vector<long long>> JohnsonAlgorithm(int V, const vector<vector<int>>& edgeList) {
    bool hasCycle;
    vector<long long> h = BellmanFord(V, edgeList, hasCycle);

    if (hasCycle) {
        cout << "The graph contains a negative weight cycle. Algorithm cannot proceed." << endl;
        return {{}};
    }

    // Reweight edges to be non-negative
    vector<vector<Edge>> adj(V);
    for (auto& e : edgeList) {
        int u = e[0], v = e[1], w = e[2];
        adj[u].push_back({v, (int)(w + h[u] - h[v])});
    }

    vector<vector<long long>> resultMatrix(V, vector<long long>(V));

    // Run Dijkstra for every vertex
    for (int s = 0; s < V; s++) {
        vector<long long> d_prime = Dijkstra(V, adj, s);
        for (int v = 0; v < V; v++) {
            if (d_prime[v] == INF) resultMatrix[s][v] = INF;
            else resultMatrix[s][v] = d_prime[v] + h[v] - h[s];
        }
    }

    return resultMatrix;
}

int main(){
  using ll=long long;
  int n,m;
  cin>>n>>m;
  vector<ll> p(n);
  for (int i=0;i<n;i++) cin>>p[i];
  vector<vector<int>> edge;
  for (int i=0;i<m;i++){
    int u,v,t;
    cin>>u>>v>>t;
    u--;v--;
    edge.push_back({u,v,t});
  }
  auto dist=JohnsonAlgorithm(n,edge);
  pair<ll,int> ans={INF,0};
  for (int i=0;i<n;i++) for (int j=0;j<n;j++){
    if (i==j) continue;
    dist[i][j]+=p[i]+p[j];
    if (ans.first==dist[i][j]) ans.second++;
    if (ans.first>dist[i][j]){
      ans.first=dist[i][j];
      ans.second=1;
    }
  }
  cout<<ans.first<<" "<<ans.second<<endl;
}