链接： H. Hellcife is on fire
题意： 大火从多个起点开始蔓延，每座城市烧毁需要一定时间，火势在两城市道路之间的速度为 1m/s; 问每座城市分别是多长时间烧完的。 思路： 把所有的起点都加入队列，然后跑最短路就好了。一开始写了个 bfs。每次拿出最小的节点，此时的值就是当前节点的答案，再用这个点去更新别的点，每个点只用一次，这样保证结果是正确的，后面发现就是 dij 的思路，用这个方法写了下最短路模板也可以过。
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<cmath> #include<cstring> #include<bitset> #include<stack> using namespace std; typedef long long ll; const int maxn=2e6+7; int t; ll vis[maxn],head[maxn],num; ll ans[maxn],val[maxn]; priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > que; pair<ll ,ll >p1,p2,p; struct node{ ll v,w,next; }e[maxn<<1]; void add(ll u,ll v,ll w){ e[num].next=head[u]; e[num].w=w; e[num].v=v; head[u]=num++; } int main (){ ll n,m,k; memset(head,-1,sizeof(head)); scanf("%lld%lld%lld",&n,&m,&k); for(ll i=0,u,v,w;i<m;i++){ scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } for(int i=1;i<=n;i++){ scanf("%lld",&val[i]); } for(ll i=0,u;i<k;i++){ scanf("%lld",&u); p1=make_pair(val[u],u); que.push(p1); } while(que.size()){ p=que.top();que.pop(); ll dis=p.first,u=p.second; if(vis[u]==1) continue; ans[u]=dis; vis[u]=1; for(int i=head[u];i!=-1;i=e[i].next){ ll to = e[i] .v, w = e[i].w; p = make_pair (dis + w + val[to] ,to); que.push(p); } } for(int i=1;i<=n;i++) printf ("%lld\n",ans[i]); }新改的最短路模板 （应该不会锅吧
#include<iostream> #include<cstdio> #include<map> #include<math.h> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=3e5+7; int vis[maxn],head[maxn],num,ans[maxn]; struct node{ int v,w,next; }e[maxn<<1]; void add(int u,int v,int w){ e[num].next=head[u]; e[num].w=w; e[num].v=v; head[u]=num++; } priority_queue<pair<int,int>, vector<pair<int, int> >, greater<pair<int, int> > > q; void dij(int s){ memset(vis,0,sizeof(vis)); q.push(make_pair(0,s)); while(q.size()) { int u=q.top().second; int dis=q.top().first; q.pop(); if(vis[u]) continue; vis[u]=1; ans[u]=dis; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; int w=e[i].w; q.push(make_pair(dis+w,v)); } } } int main (){ int n,m,s; cin>>n>>m>>s; memset(head,-1,sizeof(head)); for(int i=0,u,v,w;i<m;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); //add(v,u,w); } dij(s); for(int i=1;i<=n;i++) printf ("%d ",ans[i]); }