用wordpress编写网站,微企点做网站怎么样,怎么做视频平台网站,企业免费推广网站题意 给出一些城市电影票的价格#xff0c;以及城市之间交通的路费#xff0c;询问每一个城市怎样才能花最少的钱看到电影#xff08;看完电影还要再回来#xff09;。 题解 这是一道不太难但是挺有趣的题目。 我们这样想#xff0c;每个城市只需要查看票价比他更便宜的城…题意 给出一些城市电影票的价格以及城市之间交通的路费询问每一个城市怎样才能花最少的钱看到电影看完电影还要再回来。 题解 这是一道不太难但是挺有趣的题目。 我们这样想每个城市只需要查看票价比他更便宜的城市来更新本城市的票价就可以了是不是想到了Dijkstra求最短路的思路。 这样的话我们先从票价最便宜的城市开始从这个城市出发更新其他所有城市的票价新票价原票价2*路费然后本城市的票价就求出来了。 再重复上述操作也就是重新找一个票价最低的城市然后更新其他城市的票价这样就ok啦。 这道题还有一个巨坑会卡掉一部分人的Dijkstra的代码比如我TLE。 为什么呢 很多人写代码像这样 while(!pq.empty()){pairll,int p pq.top();pq.pop();int u p.second;for(int e head[u];e ! -1;e es[e].nxt){int v es[e].v;ll w es[e].w;if(wa[v] 2*wwa[u]){wa[v] wa[u]2*w;pq.push(make_pair(wa[v],v));}}}这样写过不了第18组测试数据因为这样一组极端数据就卡掉了 n 200000,m 199999 200000 1 2 200000 2 4 200000 3 6 200000 4 8 … 假如优先队列运行时访问点的顺序是1、2、3、…、200000 那么优先队列里面会有199999个(dist[200000],200000)点对。 而每有一个这样的点对都将会把200000的边全都遍历一边。 时间复杂度就会增加到2000002200000^22000002显然爆炸所以要把优先队列里面多余点对删掉。 在u点被取出时增加一句。 if(wa[u] p.first) continue; 至此这道题就AC啦。 ####代码
#include cstdio
#include iostream
#include algorithm
#include vector
#include queue
#include cstring
using namespace std;
typedef long long ll;
typedef pairll,int pli;
const int maxn 2e510;
priority_queuepli,vectorpli,greaterpli pq;
ll wa[maxn];
struct edge{int u,v,nxt;ll w;
}es[maxn1];
int head[maxn],vis[maxn];
int cnt 0,n,m;
void addedge(int u,int v,ll w){es[cnt].u u,es[cnt].v v,es[cnt].nxt head[u],es[cnt].w w;head[u] cnt;
}
void solve(){while(!pq.empty()){pairll,int p pq.top();pq.pop();int u p.second;if(wa[u] p.first) continue;for(int e head[u];e ! -1;e es[e].nxt){int v es[e].v;ll w es[e].w;if(wa[v] 2*wwa[u]){wa[v] wa[u]2*w;pq.push(make_pair(wa[v],v));}}}
}
int main(){memset(head,-1,sizeof(head));cinnm;for(int i 0;i m;i){int u,v;ll w;scanf(%d%d%lld,u,v,w);addedge(u,v,w);addedge(v,u,w);}for(int i 1;i n;i) {ll w;scanf(%lld,w);wa[i] w;pq.push(make_pair(w,i));}solve();for(int i 1;i n;i)printf(%lld ,wa[i]);return 0;
}
