Travel(最短路)
Travel
The country frog lives in has nn towns which are conveniently numbered by 1,2,…,n1,2,…,n.
Among n(n−1)2n(n−1)2 pairs of towns, mm of them are connected by bidirectional highway, which needs aa minutes to travel. The other pairs are connected by railway, which needs bb minutes to travel.
Find the minimum time to travel from town 11 to town nn.
Input
The input consists of multiple tests. For each test:
The first line contains 44 integers n,m,a,bn,m,a,b (2≤n≤105,0≤m≤5⋅105,1≤a,b≤1092≤n≤105,0≤m≤5⋅105,1≤a,b≤109). Each of the following mm lines contains 22integers ui,viui,vi, which denotes cities uiui and vivi are connected by highway. (1≤ui,vi≤n,ui≠vi1≤ui,vi≤n,ui≠vi).
Output
For each test, write 11 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
//题意: n , m, a, b ,其中 n 代表点数,并且是个完全图,m 是权值为 a 的边数,其余的边权值为 b ,问 1--n 的最短路
题解:如果 1 和 n 之间连边为 a 那么答案一定为 a 与一条最短的全由b组成的路径的较小者,如果 1 和 n 之间连边为b,那么答案一定
为b和一条最短的全由a组成的路径的较小者。对于第1种情况直接bfs就可以,第二种情况由于边数较多,不能直接bfs
从1开始搜索与其相连的边权为b的边,用set维护一下,由于每个点只入队1次,复杂度算是 nlogn ,叉姐的题很有意思
300ms
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <sstream>
# include <set>
# include <cmath>
# include <algorithm>
# pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
# define LL long long
# define pr pair
# define mkp make_pair
# define lowbit(x) ((x)&(-x))
# define PI acos(-1.0)
# define INF 0x3f3f3f3f3f3f3f3f
# define eps 1e-
# define MOD inline int scan() {
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
inline void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
# define MX
/**************************/
struct Edge
{
int v,nex;
}edge[MX*]; int n,m,a,b,ip;
int hlist[MX];
LL dis[MX];
bool vis[MX];
void addedge(int u,int v)
{
edge[ip]= (Edge){v,hlist[u]};
hlist[u]=ip++;
edge[ip]= (Edge){u,hlist[v]};
hlist[v]=ip++;
} void bfsB() // 1-n 连b边
{
dis[n]=INF;
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push();
dis[]=;
vis[]=;
while (!Q.empty())
{
int u = Q.front(); Q.pop();
for (int i=hlist[u];i!=-;i=edge[i].nex)
{
int v = edge[i].v;
if (!vis[v])
{
dis[v]=dis[u]+;
Q.push(v);
vis[v]=;
}
}
if (dis[n]!=INF) break;
}
printf("%lld\n",min(dis[n]*a,(LL)b));
} void bfsA() //1-n 连 a 边
{
dis[n]=INF;
set<int> st,ts;
for (int i=;i<=n;i++) st.insert(i);
set<int>::iterator it;
queue<int> Q;
Q.push();
dis[]=;
while (!Q.empty())
{
int u = Q.front(); Q.pop();
for (int i=hlist[u];i!=-;i=edge[i].nex)
{
int v=edge[i].v;
if (st.count(v)==) continue;
st.erase(v); ts.insert(v);
}
for (it=st.begin();it!=st.end();it++)
{
dis[*it] = dis[u]+;
Q.push(*it);
}
if (dis[n]!=INF) break;
st.swap(ts);
ts.clear();
}
printf("%lld\n",min(dis[n]*b,(LL)a));
} int main()
{
while(scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF)
{
memset(hlist,-,sizeof(hlist));
ip=;
bool flag=;
for (int i=;i<m;i++)
{
int u = scan();
int v = scan();
addedge(u,v);
if (u>v) swap(u,v);
if (u==&&v==n) flag=;
}
if (flag)
{
if (a<b) printf("%d\n",a);
else bfsA();
}
else
{
if (b<a) printf("%d\n",b);
else bfsB();
}
}
return ;
}
最新文章
- ASP.NET 5 已死 - 隆重介绍 ASP.NET Core 1.0 和 .NET Core 1.0
- 多线程编程4 - NSOperationQueue
- 如何使用R语言解决可恶的脏数据
- 30分钟入门Java8之默认方法和静态接口方法
- sicily 1022. Train Problem
- 高性能I/O设计模式Reactor和Proactor
- Codeforces 577B Modulo Sum
- 在Android Studio中进行单元测试和UI测试
- TCP协议和UDP协议的区别
- Hadoop(九)Hadoop IO之Compression和Codecs
- 简单的纯js三级联动
- find your present (2) hdoj 2095
- 【Java基础】【18Map集合&;模拟斗D主X排和F排】
- idea 编译报错 未结束的字符串字面值,非法的类型开始
- CNN卷积层:ReLU函数
- 9. 一个list拆分成多个list返回
- hibernate增删改
- 机器学习基石笔记:16 Three Learning Principles
- Web 项目遇到的乱码问题
- 【并查集】 不相交集合 - 并查集 教程(文章作者:Slyar)