美文网首页
没事刷刷Codeforces

没事刷刷Codeforces

作者: 恰似一碗咸鱼粥 | 来源:发表于2019-04-06 17:52 被阅读0次

1.601A The Two Routes

其实对于边权为1的最短路用bfs也是可以的,但是为了练习还是用了dijkstra啦~

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
bool e[410][410];
int dis1[410],dis2[410];
bool vis1[410],vis2[410];
int n,m;

void dijkstra(int u){
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    memset(vis1,false,sizeof(vis1));
    memset(vis2,false,sizeof(vis2));
    dis1[u]=dis2[u]=0;
    for(int i=0;i<n;++i){
        int mind=inf,mint=-1;
        for(int j=1;j<=n;++j){
            if(!vis1[j]&&dis1[j]<mind){
                mind=dis1[j];
                mint=j;
            }
        }
        if(mint==-1)break;
        vis1[mint]=true;
        for(int j=1;j<=n;++j){
            if(!vis1[j]&&e[j][mint]&&dis1[j]>dis1[mint]+1){
                dis1[j]=dis1[mint]+1;
            }
        }
    }
    for(int i=0;i<n;++i){
        int mind=inf,mint=-1;
        for(int j=1;j<=n;++j){
            if(!vis2[j]&&dis2[j]<mind){
                mind=dis2[j];
                mint=j;
            }
        }
        if(mint==-1)break;
        vis2[mint]=true;
        for(int j=1;j<=n;++j){
            if(!vis2[j]&&!e[j][mint]&&dis2[j]>dis2[mint]+1){
                dis2[j]=dis2[mint]+1;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;++i){
        cin>>u>>v;
        e[u][v]=e[v][u]=true;
    }
    dijkstra(1);
    int ans=max(dis1[n],dis2[n]);
    ans==inf?cout<<-1<<endl:cout<<ans<<endl;
    return 0;
}

相关文章

  • 没事刷刷Codeforces

    1.601A The Two Routes 其实对于边权为1的最短路用bfs也是可以的,但是为了练习还是用了dij...

  • 没事刷刷锅

    喜欢听相声,说的好的不爱听,就喜欢听砸锅(郭)的相声。太少了。口味儿重点儿也行,麻辣小涮锅(郭)之类。撸着串儿,举...

  • 没事就爱刷刷朋友圈

    有事没事刷刷朋友圈,似乎已经成为了绝大多数人的生活情趣。 这样的画面习以为常的出现在世界各地的各个角落中,拥挤的地...

  • 微信搜完这些,我和男朋友差点分手

    最近没法出门,每天都是刷刷刷刷刷刷刷手机。 朋友圈已经有人哀嚎:真的没事干了。 可是这两天,我精神得很。起因是那天...

  • “我的安全感”

    闲来没事刷刷微博,而对方也闲来没事刷刷即刻 我们的闲暇时间总是穿插着这些神奇的资讯社交app。 倒也不是说这样并不...

  • 刷刷刷

    时间刷刷刷的流失了, 它让我们变得越来越高,它让我们长大了。 而父亲母亲慢慢的老去了,脸上有这一道道皱纹。 时间刷...

  • 刷刷刷

    刷刷 刷刷刷 刷刷 刷什么 刷刷 刷手机 刷刷 时时刷 刷刷 处处刷 起床 刷刷刷 临睡 刷刷刷 有空 使劲刷 没...

  • 刷刷刷

    “人们的很多自主选择其实严格来说都不能算是完全的自主,因为我们无时无刻不在被引导着,而且是不知不觉。”有一种方...

  • 刷刷刷

    刷刷刷。 有点受不了了。 小刘似乎得了亢奋型精神狂燥症。 从卧室到客厅,再从客厅到卧室,来来回回,如热锅上的蚂蚁一...

  • 刷刷刷

    抖音刷多了,没意思! 微博刷多了,不真实! 公众号看多了,没营养! 我发出灵魂拷问: 人就不能刷刷手机,简简单单地...

网友评论

      本文标题:没事刷刷Codeforces

      本文链接:https://www.haomeiwen.com/subject/lmzriqtx.html