Poj 3255(dijkstra求次短路)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 5500, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
struct edge
{
  int to;
  int cost;
};
vector<edge>g[N];
int m, n;
int d1[N];
int dis2[N];
void dijkstra()
{
  priority_queue<PII, vector<PII>, greater<PII> >q;
  fill(d1 + 1, d1 + 1 + n, INF);
  fill(dis2 + 1, dis2 + 1 + n, INF);
  d1[1] = 0;
  q.push({0, 1});
  while (q.size())
  {
    PII t = q.top();
    q.pop();
    int v = t.second, d = t.first;
    if (dis2[v] < d) continue;
    for (int i = 0; i < g[v].size(); i++)
    {
      edge x = g[v][i];
      int d2 = d + x.cost;
      if (d1[x.to] > d2)
      {
        swap(d1[x.to], d2);
        q.push({d1[x.to], x.to});
      }
      if (dis2[x.to] > d2 && d2 > d1[x.to])
      {
        dis2[x.to] = d2;
        q.push({dis2[x.to], x.to});
      }
    }
  }
}
int main()
{
  while (~scanf("%d%d", &n, &m))
  {
    for (int i = 1; i <= m; i++)
    {
      int x, y, z;
      cin >> x >> y >> z;
      g[x].push_back({y, z});
      g[y].push_back({x, z});
    }
    dijkstra();
    cout << dis2[n] << endl;
    return 0;
  }
}