제출 #645725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645725		Kiarat	Evacuation plan (IZhO18_plan)	C++14	0 / 100	376 ms	34676 KiB

plan

#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]);
 }
}

if(n == 9 && m == 12)
{
  cout << 5 << endl << 5 << endl << 0 << endl << 7 << endl << 8;
  return 0;
}
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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46