SCU - 4444 别样最短路径-大数据完全图

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=184147

Travel

The country frog lives in has n towns which are conveniently numbered by 1,2,…,n. Among n(n−1)2 pairs of towns, m of them are connected by bidirectional highway, which needs a minutes to travel. The other pairs are connected by railway, which needs b minutes to travel. Find the minimum time to travel from town 1 to town n.

Input

The input consists of multiple tests. For each test: The first line contains 4 integers n,m,a,b (2≤n≤105,0≤m≤5⋅105,1≤a,b≤109). Each of the following m lines contains 2integers ui,vi, which denotes cities ui and vi are connected by highway. (1≤ui,vi≤n,ui≠vi).

Output

For each test, write 1 integer which denotes the minimum time.

Sample Input

3 2 1 3 1 2 2 3 3 2 2 3 1 2 2 3

Sample Output

2 3

题意：

给定一个完全图，其中有两种边，长度为a（不超过5e5）或长度为b（剩下的），求有1~n的最短路径（数据范围1e5）

#include<iostream> #include<algorithm> #include<queue> #include<vector> #include<cstring> #include<set> using namespace std; #define inf 0x3f3f3f3f struct node { int v,val; node(int w,int x):v(w),val(x) {} bool friend operator<(const node a,const node b) { return a.val>b.val; } }; struct Egda { int v,val,next; }eadg[1000010]; int head[1000010],p; int n,m,a,b; inline void add(int u,int v,int val) { eadg[p].v=v; eadg[p].val=val; eadg[p].next=head[u]; head[u]=p++; } int dis[1000010]; int vis[1000010]; void dijk() { priority_queue<node>q; memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[1]=0; q.push(node(1,dis[1])); while(!q.empty()) { node ss=q.top(); q.pop(); if(vis[ss.v]) continue; vis[ss.v]=1; for(int i=head[ss.v];~i;i=eadg[i].next) { if(!vis[eadg[i].v]&&dis[eadg[i].v]>dis[ss.v]+eadg[i].val) { dis[eadg[i].v]=dis[ss.v]+eadg[i].val; q.push(node(eadg[i].v,dis[eadg[i].v])); } } } cout<<(dis[n]<b?dis[n]:b)<<endl; } void bfs() { dis[1]=0; dis[n]=inf; set<int>q,e; set<int>::iterator it; q.clear(); e.clear(); for(int i=2;i<=n;i++) q.insert(i); queue<int>qq; qq.push(1); while(!q.empty()) { int o=qq.front(); qq.pop(); for(int i=head[o];~i;i=eadg[i].next) { if(q.count(eadg[i].v)) { q.erase(eadg[i].v); e.insert(eadg[i].v); } } for(it=q.begin();it!=q.end();it++) { dis[*it]=dis[o]+1; qq.push(*it); } q=e; e.clear(); } cout<<(a<dis[n]*b?a:dis[n]*b)<<endl; } int main() { while(cin>>n>>m>>a>>b) { p=0; memset(head,-1,sizeof(head)); int flag=0; for(int i=0;i<m;i++) { int u,v,val=a; cin>>u>>v; if(u>v) swap(u,v); add(u,v,val); add(v,u,val); if(u==1&&v==n) flag=1; } if(a==b) cout<<a<<endl; else if(!flag) { dijk(); } else { bfs(); } } return 0; }

这道题很6，set用的很巧妙。 这道题分两种情况

---

1. 1-n没有直连的公路，这个好找，直接dijk求最短路就行 2. 1-n没有公路，如果我们直接求由于情况多不行，（为啥不行，我也不知道。。），所以用set来存下无法用铁路到达的点，然后更新这些点，（bfs）dis存的是通过多少次铁路能从1到达那个点（太神奇了。。）

---

好6的题目，大佬的想法就是神奇

最后附上我参考的大佬博客: 神奇的传送门