最短路之Dijkstra+堆优化（单源最短路）

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int>p;
const int maxn = 205;
int d[maxn];
int n, m;
vector<p>vec[maxn];
void init() {
  for (int i = 0;i <= n;++i)d[i] = INF;
  for (int i = 0;i < maxn;++i)vec[i].clear();
}
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    init();//初始化
    for (int i = 0;i < m;++i) {//读边
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      vec[x].push_back(make_pair(z, y));
      vec[y].push_back(make_pair(z, x));
    }
    priority_queue<p, vector<p>, greater<p>>pq;//定义由小到大的优先队列
    int s, t;
    scanf("%d%d", &s, &t);
    d[s] = 0;
    pq.push(make_pair(d[s], s));//将第一个元素入队
    while (!pq.empty()) {
      int now = pq.top().second;//now现在是与第一个顶点距离最近的顶点 
      pq.pop();//通过now实现对其他边的松弛操作
      for (int i = 0;i < vec[now].size();++i) {
        int v = vec[now][i].second;
        if (d[v] > d[now] + vec[now][i].first) {
          d[v] = d[now] + vec[now][i].first;
          pq.push(make_pair(d[v], v));//将松弛后的边入队
        }
      }
    }
    if (d[t] == INF)printf("-1\n");
    else printf("%d\n", d[t]);
  }
  return 0;
}