题意：有n个点和m条路（都收费），n个点在开演唱会，门票不同，对于生活在n个点的小伙伴，要求计算出每个小伙伴为了看一场演唱会要花费的最小价格；
思路：
这道题我一开始觉得要对每一个点都跑一次最短路，
然而只用把dis【】的每个点初始化成每个地方的门票价格，在放入优先队列中，接着再跑一遍Dijkstra；
对Dijkstra刷新了认识。至于原理：
(可以想明白，每次在队列中找到最小的门票价格去更新（松弛）；
注意路费要计算来回；
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef long long ll; const int maxn = 200000+7; vector<pair<int,ll> >mp[maxn]; priority_queue<pair<ll,int> >q; ll dis[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; ll c; scanf("%d%d%I64d",&u,&v,&c); //因为long long 和int ；还有%I64d，wa了多次； mp[u].push_back(make_pair(v,c*2)); mp[v].push_back(make_pair(u,c*2)); } for(int i=1;i<=n;i++) { ll x; scanf("%I64d",&x); dis[i]=x; q.push(make_pair(-dis[i],i)); } while(!q.empty()) { int now = q.top().second; ll w = q.top().first; q.pop(); if(dis[now] != -w)continue; //这一步也比较重要；既然这个点被其他点松弛过，就不能去松弛别点； for(int t=0;t<mp[now].size();t++) { int to = mp[now][t].first; if(dis[to]>dis[now]+mp[now][t].second) { dis[to]=dis[now]+mp[now][t].second; q.push(make_pair(-dis[to],to)); } } } for(int i=1;i<=n;i++) { printf("%I64d%c",dis[i],i==n?' ':' '); } return 0; }