Submission #12951465

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2100000000
#define LLINF 10000000000000000ll
#define MOD 1000000007

bool dbgflag = true; //debug

struct edge {
  ll cost;
  ll to;
};

void dijkstra(int s, vector<ll>&d, vector<vector<edge>>&graph) {
  //for (int i = 0; i < d.size(); i++) d[i] = LLINF;
  priority_queue<pll, vector<pll>, greater<pll>> que;

  d[s] = 0;
  que.push(pll(0, s));

  while(!que.empty()) {
    pll p = que.top();
    que.pop();
    ll v = p.second;

    if (d[v] < p.first) continue;

    for (edge e: graph[v]) {
      if (d[e.to] < d[v] + e.cost) continue;
      d[e.to] = d[v] + e.cost;
      que.push(pll(d[e.to], e.to));
    }
  }
  return;
}

void init_d(vector<ll>&d) {
  for (int i = 0; i < d.size(); i++) d[i] = LLINF;
  return;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;
  vector<ll> d(n, LLINF);
  vector<vector<edge>> graph(n, vector<edge>());
  
  for (int i = 0; i < k; i++) {
    int op;
    cin >> op;
    if (op == 0) {
      int a, b;
      cin >> a >> b;
      a--; b--;
      dijkstra(a, d, graph);
      cout << ((d[b] == LLINF) ? -1 : d[b]) << endl;
      init_d(d);
    }
    else if (op == 1) {
      int c, d, e;
      cin >> c >> d >> e;
      c--; d--;
      edge e1, e2;
      e1.to = c; e1.cost = e;
      e2.to = d; e2.cost = e;
      graph[c].push_back(e2);
      graph[d].push_back(e1);
    }
  }
}

Submission Info

Judge Result