結果

問題 No.614 壊れたキャンパス
ユーザー ふっぴーふっぴー
提出日時 2017-12-14 13:18:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,641 bytes
コンパイル時間 2,319 ms
コンパイル使用メモリ 195,068 KB
実行使用メモリ 146,456 KB
最終ジャッジ日時 2024-12-14 12:39:58
合計ジャッジ時間 21,374 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
22,628 KB
testcase_01 AC 8 ms
90,808 KB
testcase_02 AC 8 ms
22,648 KB
testcase_03 AC 8 ms
15,688 KB
testcase_04 AC 8 ms
15,728 KB
testcase_05 AC 8 ms
15,664 KB
testcase_06 AC 8 ms
15,808 KB
testcase_07 AC 8 ms
15,700 KB
testcase_08 AC 1,285 ms
90,512 KB
testcase_09 AC 1,533 ms
90,320 KB
testcase_10 TLE -
testcase_11 AC 1,427 ms
91,524 KB
testcase_12 AC 1,515 ms
91,396 KB
testcase_13 AC 1,427 ms
91,968 KB
testcase_14 AC 1,327 ms
91,908 KB
testcase_15 TLE -
testcase_16 AC 1,244 ms
90,704 KB
testcase_17 AC 716 ms
86,020 KB
testcase_18 AC 638 ms
74,664 KB
testcase_19 AC 705 ms
146,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e18 * 2;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
static const int N=400020;

vector< vector<pll> > adj(N,vector<pll>());
vl d(N,INF);
map<pll, ll> mp;
int cnt = 1;



void dijkstra(){
  priority_queue<pll, vector<pll>, greater<pll> > pq;
  int i;
  vi color(cnt - 1,WHITE);
	
  d[1]=0;
  pq.push(make_pair(0,1));
  color[1]=GRAY;
	
  while(!pq.empty()){
    pll f=pq.top();
    pq.pop();
    ll u=f.second;
    color[u]=BLACK;
    if(d[u]<f.first){
      continue;
    }
    for (i = 0; i < adj[u].size(); i++){
      ll v=adj[u][i].second;
      if(color[v]==BLACK){
	continue;
      }
      if(d[v]>d[u]+adj[u][i].first){
	d[v]=d[u]+adj[u][i].first;
	pq.push(make_pair(d[v],v));
	color[v]=GRAY;
      }
    }
  }
}
	 



int main() {
  int n, m, k, s, t, i;
  cin >> n >> m >> k >> s >> t;
  s--; t--;
  vector<set<ll> > floor(n);
  floor[0].insert(s);
  floor[n - 1].insert(t);
  mp[pll(0, s)] = cnt++;
  mp[pll(n - 1, t)] = cnt++;
  for (i = 0; i < m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--; c--;
    if (mp[pll(a, b)] == 0) {
      mp[pll(a, b)] = cnt++;
      floor[a].insert(b);
    }
    if (mp[pll(a + 1, c)] == 0) {
      mp[pll(a + 1, c)] = cnt++;
      floor[a + 1].insert(c);
    }
    adj[mp[pll(a, b)]].push_back(pll(0, mp[pll(a + 1, c)]));
  }
  for (i = 0; i < n; i++) {
    auto pre = floor[i].begin();
    auto itr = floor[i].begin();
    itr++;
    for (; itr != floor[i].end(); itr++, pre++) {
      ll a = *pre, b = *itr;
      //cout << i << " " << a << " " << b << endl;
      ll u = mp[pll(i, a)], v = mp[pll(i, b)];
      adj[u].push_back(pll(abs(b - a), v));
      adj[v].push_back(pll(abs(a - b), u));
    }
  }
  dijkstra();
  if (d[mp[pll(n - 1, t)]] == INF) {
    cout << -1 << endl;
  }
  else {
    cout << d[mp[pll(n - 1, t)]] << endl;
  }
}

/*
2 1 5 1 5
1 3 4

2 2 10 10 1
1 9 5 
1 6 1

2 0 5 1 5
*/
0