codeforces #333 div 2 C. The Two Routes

Posted by 111qqz on Tuesday, December 22, 2015

TOC

http://codeforces.com/problemset/problem/602/C
题意:给出n个城镇,m条双向铁路,对于任意不同的x,y,如果x,y之间没有铁路,那么一定有双向公路。train只能走铁路,bus只能走公路。现在一辆火车和一辆bus同时从1出发,要到达n,处于安全考虑,bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达,那么输出-1.
思路:n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意,一定存在一条1到n的路,不是公路就是铁路。那么就让有路的花费1的代价到n,然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。

/* ***********************************************
Author :111qqz
Created Time :2015年12月22日 星期二 16时28分59秒
File Name :code/cf/#333/C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=4E2+7;
int n ,m;
int road[N][N];
int rail[N][N];

int floyd()
{
    for ( int k = 1 ; k <= n ; k++)
    for ( int i = 1 ; i <= n ; i++)
        for ( int j = 1 ; j <= n ; j++)
        if (rail[i][j]>rail[i][k]+rail[k][j]) rail[i][j] = rail[i][k] + rail[k][j];
    if (rail[1][n]==inf) return -1;
    else return rail[1][n];
}

int floyd2()
{
    for ( int k = 1 ; k <= n ; k++)
    for ( int i =1 ;  i <= n ; i++)
        for ( int j = 1 ; j <= n ;j++)
        road[i][j] = min(road[i][j],road[i][k]+road[k][j]);
    if (road[1][n]==inf) return -1;
    else return road[1][n];

}

void init()
{
  //  for ( int i = 0 ; i <= 400 ; i++)
//	for ( int j = 0 ; j <= 400 ; j ++)
//	{
//	    rail[i][j] = 99999;
//	    road[i][j]=  99999;
//	}
    ms(rail,0x3f);
    ms(road,0x3f);
}

int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    cin>>n>>m;
    init();
//	cout<<road[1]<<inf<<endl;
    for ( int i = 0 ; i < m ; i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        rail[u][v] = 1;
        rail[v][u] = 1;
    }
	
    for ( int i = 1 ; i <= n-1 ; i++)
    {
        for ( int j = i+1 ; j <= n ; j++)
        {
    //	cout<<"aaaa?"<<endl;
        if (rail[i][j]==inf)
        {
            road[i][j] = 1;
            road[j][i] = 1;
        }
        }
    }
    int ans;
    if (rail[1][n]==1)
    {
        ans = floyd2();
        cout<<ans<<endl;
    }
    else
    {
	    
     //   cout<<"aaa?"<<endl;
        ans = floyd();
        cout<<ans<<endl;
    }


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付