はやし屋

競技プログラミングのメモ きたない

KUPC 2013 F - 7歳教

http://kupc2013.contest.atcoder.jp/tasks/kupc2013_f

ワーシャルフロイドやってやるのはわかった。

ダイクストラで TLE になってしまったので
priorityけして幅優先にしたら AC した。

ノードをソートするときにおもくなるのかな...

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;

typedef pair < int , int > Pi;

#define fr first 
#define sc second

int n , s ;
int l[555] , r[555];
int w[555][555];


int main(){

  cin >> n >> s ;
  s--;

  for(int i = 0 ; i < n ; ++i){
    cin >> l[i] >> r[i];
  }

  for(int i = 0 ; i < n ; ++i){
    for(int j = 0 ; j < n ; ++j){
      cin >> w[i][j];
    }
  }

  for(int k = 0 ; k < n ; ++k)
    for(int i = 0 ; i < n ; ++i)
      for(int j = 0 ; j < n ; ++j)
	w[i][j] = min(w[i][j],w[i][k]+w[k][j]);


  // cost , v
  //priority_
  queue < Pi > que;

  vector < int > time(n) ;

  for(int i = 0 ; i < n ; ++i){
    int arrive = max(l[i],w[s][i]);
    int leave = max(r[i],arrive);
    que.push(make_pair(leave,i));
    time[i] = leave - arrive;
  } 

  while(!que.empty()){
    //    Pi p = que.top();que.pop();
    Pi p = que.front();que.pop();
    for(int i = 0 ; i < n ; ++i){
      int arrive = max(l[i],p.fr + w[p.sc][i]);
      int leave = max(r[i],arrive);
      if(leave > arrive && time[i] < time[p.sc] + (leave - arrive) ){
	time[i] = time[p.sc] + (leave - arrive) ;
	que.push(make_pair(leave,i));
      }
    }
  }

  cout << max(0,*max_element(time.begin(),time.end())) << endl;
}