oj.uz

답안 #645726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
645726 2022-09-27T18:03:09 Z Kiarat Evacuation plan (IZhO18_plan) C++14
0 / 100
 383 ms 34672 KB 
#include <bits/stdc++.h>

#define pb push_back 
using namespace std;
typedef long long ll;

ll a[100001];
ll ans=0,cnt=0,k=0;

const ll INF=1e18;




long long d[100100];
vector < pair<ll, ll> > g[100100];
ll p[100100];

vector <ll> vt[1001];
int main()
{
  
  ll n,m;
  cin >> n >> m;
   


    for(int i=1;i<=m;i++){
      ll x,y,w;
      cin >> x >> y >> w;

      g[x].push_back({y,w});
      g[y].push_back({x,w});

    }
  
   ll k;
   cin >> k;
   ll b[k+1];

   for(int i=1;i<=k;i++)
   {
    cin >> b[i];
   }
   ll op;
   cin >> op;
   pair <ll,ll> pr[op+1];
   for(int i=1;i<=op;i++)
   {
    cin >> pr[i].first >> pr[i].second;
   }

  
  for(int qp = 1;qp<=k;qp++)
  {
  
 
  for(int i = 1; i <= n; i++) d[i] = INF;
  ll s = b[qp];
  d[s] = 0;

  set < pair<long long,ll> > q;
  q.insert (make_pair (d[s], s));
  while (!q.empty()) {
    int v = q.begin()->second;
    q.erase (q.begin());
 
    for (size_t j=0; j<g[v].size(); ++j) {
      int to = g[v][j].first,
        len = g[v][j].second;
      if (d[v] + len < d[to]) {
        q.erase (make_pair (d[to], to));
        d[to] = d[v] + len;
        p[to] = v;
        q.insert (make_pair (d[to], to));
      }
    }
  }
  
 for(int pp = 1;pp<=op;pp++)
 {
  vt[pp].push_back(d[pr[pp].second]);
    vt[pp].push_back(d[pr[pp].first]);
 }
}


for(int i=0;i<=op;i++)
{
  sort(vt[i].begin(),vt[i].end());
}

for(int i=0;i<=op;i++)
{
  
cout << vt[i][0];

  cout << endl;
}
  

}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 34672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -