专栏首页Zaqdt_ACM51nod 1649 齐头并进(Codeforces 601A The Two Routes) (最短路)

51nod 1649 齐头并进(Codeforces 601A The Two Routes) (最短路)

题目链接(Codeforces):http://codeforces.com/problemset/problem/601/A

题目链接(51nod):https://www.51nod.com/Challenge/Problem.html#!#problemId=1649

       51nod的题面是中文的

       思路就是两种车各跑一遍dij,就是处理一下边就好了。


AC代码:

#include <bits/stdc++.h>
#define maxm 200005
#define maxn 405
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
	int to,w,next;
	bool operator < (const Node &a) const {
		return a.w < w;
	}
}Edge[maxm],S,Next;
int head[maxm],num;
int dist[maxm];
bool a[maxn][maxn],vis[maxm];
int n,m;

void init(){
	for(int i=0;i<=n;i++){
		head[i] = -1;
	}
	num = 0;
}

void add(int u,int v){
	Edge[num].w = 1;
	Edge[num].to = v;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void dijkstra(int s){
	for(int i=0;i<=n;i++){
		dist[i] = inf;
		vis[i] = false;
	}
	priority_queue<Node> q;
	S.to = s;
	dist[s] = 0;
	q.push(S);
	while(!q.empty()){
		int u = q.top().to;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i=head[u];i!=-1;i=Edge[i].next){
			int v = Edge[i].to;
			if(!vis[v] && dist[v] > dist[u] + Edge[i].w){
				dist[v] = dist[u] + Edge[i].w;
				Next.to = v;
				Next.w = dist[v];
				q.push(Next);
			}
		}
	}
}

int main()
{
	// init();
	scanf("%d%d",&n,&m);
	init();
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		a[u][v] = a[v][u] = true;
		add(u, v);
		add(v, u);
	}
	dijkstra(1);
	int ans1 = dist[n];
	init();
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i][j] == false){
				add(i, j);
				add(j, i);
			}
		}
	}
	dijkstra(1);
	int ans2 = dist[n];
	printf("%d\n",max(ans1, ans2) == inf ? -1 : max(ans1, ans2));
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • 2018年第九届蓝桥杯B组题解

    按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

    Ch_Zaqdt
  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • BZOJ2655: calc(dp 拉格朗日插值)

    设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数

    attack
  • HPU personal-training 2

    A - Kefa and Park 题意:就是一棵树,然后本人的家在根上,餐厅在叶子节点上。然后在前往叶子结点的餐厅的时候,途中的结点上有猫,而这个人特别怕...

    用户7727433
  • 最佳加法表达式 DP

    有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少。 输入: 5 3 1 2 3 4 5 ...

    ACM算法日常
  • PAT 1004 Counting Leaves

    1004. Counting Leaves (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • LeetCode31|打印从1到最大的n位数

    这道题算是api的使用方式了,数据的计算,其实自己也没有什么好说的了,但是由于文章的字数必需要达到300字,所有有些时候就只好在这里唠会嗑了,因为文章的原创对于...

    后端Coder
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack

扫码关注云+社区

领取腾讯云代金券