Submission #4243058

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, m; cin >> n >> m;
  vector<vector<pair<int, long long> > > edge(n);
  REP(i, m) {
    int f, t; cin >> f >> t;
    long long c; cin >> c;
    edge[f].emplace_back(t, c);
    edge[t].emplace_back(f, c);
  }
  vector<vector<long long> > dist(n, vector<long long>(28, LINF));
  dist[0][0] = 0;
  priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > que;
  que.emplace(0, 0);
  while (!que.empty()) {
    auto au = que.top(); que.pop();
    long long cost = au.first;
    int ver = au.second;
    if (dist[ver][cost%28] < cost || ver == n-1) continue;
    for (auto e : edge[ver]) {
      long long nx_cost = dist[ver][cost%28] + e.second;
      if (nx_cost < dist[e.first][nx_cost%28]) {
        dist[e.first][nx_cost%28] = nx_cost;
        que.emplace(nx_cost, e.first);
      }
    }
  }
  cout << min({dist[n-1][0], dist[n-1][4], dist[n-1][7], dist[n-1][8], dist[n-1][12], dist[n-1][14], dist[n-1][16], dist[n-1][20], dist[n-1][21], dist[n-1][24]}) << '\n';
  return 0;
}

Submission Info

Judge Result