練習帳

■ [練習][Codeforces] Codeforces Beta Round #77 Div2. D Volleyball 続き 20:11

　前回，n=1000に対するワーシャルフロイドを行ってTLEを起こしたところまでで終わっていたのでその続きを行います．結論を先に言うと，ネックはここだけではなく，後段のコストを求めるためにダイクストラ法を行っている部分でも不適切な箇所がありました．

分析

　2点間の最短距離を求める方法をワーシャルフロイド法からダイクストラ法に変更．今回の場合，道の本数mがジャンクション同士を結ぶ場合の数n**2に比べて十分小さいのでこちらの方が速くなります．きちんと速くするために，2つのジャンクション間の距離の情報を持ちかたを

ll table[1111][1111]

から

vector<vector<pair<int, ll> > > table

に変更しています．

　これできちんと間に合うと思ったのですが，同じテストケースでTLEがでました．調べてみると，2つのジャンクション間の最短距離を求めるところではなく，2回目のダイクストラ法を行う部分で時間がかかっている様子．よくよくコードを見てみると，前回のコードの次の部分がいけませんでした．

    while(!q.empty()){
       ・・・（省略）・・・
      for(int i = 0;i < n;i++){
	if(table[i][now] != -1 && t[now] >= table[i][now] && used[i] != 1 ){
	  q.push(i);
	}
      }
    }

　あるジャンクションから次に探索するジャンクションを探して，キューに入れる部分のコードですが，キューに入れたらすぐに探索済みのマークをつけておかないと，同じ点を何回もキューに入れてしまう事になってしまいます．

    while(!q.empty()){
       ・・・（省略）・・・
      for(int i = 0;i < n;i++){
	if(table[i][now] != -1 && t[now] >= table[i][now] && used[i] != 1 ){
	  q.push(i);
          used[i] = 1; // <- 追加
	}
      }
    }

と1行追加します．前述のデータの持ち方と併せると最終的につぎのようになり，acceptされました．

コード例

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <cstring>

using namespace std;

typedef long long ll;

int x, y;
vector<int> t;
vector<int> c;

vector<vector<pair<int, ll > > > dist;  // 2点間を直接結ぶ道路の距離
vector<vector<pair<int, ll > > > table; // 2点間の最短距離
ll table_sparse[1111][1111]; // distからtableを作る為の中間データ

int n, m;

void calcTable(int start){
  queue<int> q;
  int used[1111] = {};
  q.push(start);
  table_sparse[start][start] = 0;
  used[start] = 1;

  while(!q.empty()){
    int now = q.front();
    q.pop();
    used[now] = 1;
    for(int i = 0; i < dist[now].size(); i++){
      ll next = dist[now][i].first;
      ll distance = dist[now][i].second;
      if(next!=now && distance!=-1 && (table_sparse[start][next] == -1 || table_sparse[start][now] + distance < table_sparse[start][next])){
	table_sparse[start][next] = table_sparse[start][now] + distance;
      }
    }

    for(int i = 0;i < dist[now].size();i++){
      ll next = dist[now][i].first;
      ll distance = dist[now][i].second;
      if(next!=now && distance != -1&& used[next] == 0){
	q.push(next);
      }
    }
  }
}

int main(){
  
  while(cin >> n >> m){
    int x, y;cin >> x >> y;
    x --;y--;

    dist.clear(); dist.resize(n);
    memset(table_sparse, -1, sizeof(table_sparse));

    for(int i = 0;i < m;i++){
      int u, v, w;cin >> u >> v >> w;
      u --;v--;
      dist[u].push_back(make_pair(v, w));
      dist[v].push_back(make_pair(u, w));
    }

    for(int i = 0;i < n;i++){
      calcTable(i);
    }

    table.clear();table.resize(n);
    for(int i = 0;i < n;i++){
      for(int j = 0;j < n;j++){
	if(table_sparse[i][j] !=-1){
	  table[i].push_back(make_pair(j, table_sparse[i][j]));
	  table[j].push_back(make_pair(i, table_sparse[i][j]));
	}
      }
    }

    t.clear();t.resize(n);
    c.clear();c.resize(n);
    for(int i = 0;i < n;i++){
      cin >> t[i] >> c[i];
    }

    vector<int> used(n);
    vector<ll> cost(n, -1);
    cost[x] = 0;
    queue<int> q;
    q.push(x);

    while(!q.empty()){
      int now = q.front();
      used[now] = 1;
      q.pop();
      for(int i = 0;i < table[now].size();i++){
	int next = table[now][i].first;
	ll distance = table[now][i].second;
	if(distance != -1 && t[now] >= distance && (cost[next] == -1 || cost[next] >= cost[now] + c[now]) ) {
	  cost[next] = cost[now] + c[now];
	}
      }

      for(int i = 0;i < table[now].size();i++){
	int next = table[now][i].first;
	ll distance = table[now][i].second;
	  
	if(t[now] >= distance && used[next] != 1 ){
	  q.push(next);
	  used[next] = 1;
	}
      }
    }

    cout << cost[y] <<endl;
  }
}

ツイートする