专栏首页算法修养CodeForces 666B World Tour(spfa+枚举)

CodeForces 666B World Tour(spfa+枚举)

B. World Tour

time limit per test

5 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

A famous sculptor Cicasso goes to a world tour!

Well, it is not actually a world-wide. But not everyone should have the opportunity to see works of sculptor, shouldn't he? Otherwise there will be no any exclusivity. So Cicasso will entirely hold the world tour in his native country — Berland.

Cicasso is very devoted to his work and he wants to be distracted as little as possible. Therefore he will visit only four cities. These cities will be different, so no one could think that he has "favourites". Of course, to save money, he will chose the shortest paths between these cities. But as you have probably guessed, Cicasso is a weird person. Although he doesn't like to organize exhibitions, he likes to travel around the country and enjoy its scenery. So he wants the total distance which he will travel to be as large as possible. However, the sculptor is bad in planning, so he asks you for help.

There are n cities and m one-way roads in Berland. You have to choose four different cities, which Cicasso will visit and also determine the order in which he will visit them. So that the total distance he will travel, if he visits cities in your order, starting from the first city in your list, and ending in the last, choosing each time the shortest route between a pair of cities — will be the largest.

Note that intermediate routes may pass through the cities, which are assigned to the tour, as well as pass twice through the same city. For example, the tour can look like that: 

. Four cities in the order of visiting marked as overlines:[1, 5, 2, 4].

Note that Berland is a high-tech country. So using nanotechnologies all roads were altered so that they have the same length. For the same reason moving using regular cars is not very popular in the country, and it can happen that there are such pairs of cities, one of which generally can not be reached by car from the other one. However, Cicasso is very conservative and cannot travel without the car. Choose cities so that the sculptor can make the tour using only the automobile. It is guaranteed that it is always possible to do.

Input

In the first line there is a pair of integers n and m (4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000) — a number of cities and one-way roads in Berland.

Each of the next m lines contains a pair of integers ui, vi (1 ≤ ui, vi ≤ n) — a one-way road from the city ui to the city vi. Note that uiand vi are not required to be distinct. Moreover, it can be several one-way roads between the same pair of cities.

Output

Print four integers — numbers of cities which Cicasso will visit according to optimal choice of the route. Numbers of cities should be printed in the order that Cicasso will visit them. If there are multiple solutions, print any of them.

Example

input

8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5

output

2 1 8 7

Floyed求最短路回超时,用spfa然后再枚举4个点中的中间两个点,头尾两个点

只需要取最大的就好了,当然不能有重复

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;
const int INF=1000000;
#define MAX 3000
vector < pair<int,int> > a[MAX+5];
vector < pair<int,int> > b[MAX+5];
vector <int> c[MAX+5];
int d[MAX+5][MAX+5];
bool vis[MAX+5];
int res[5];
int n,m;
void spfa(int i)
{
   memset(vis,false,sizeof(vis));
   queue<int> q;
   q.push(i);vis[i]=1;
   while(!q.empty())
   {
       int x=q.front();q.pop();
       vis[x]=0;
       for(int j=0;j<c[x].size();j++)
       {
           int next=c[x][j];
           if(d[i][next]>d[i][x]+1)
           {
               d[i][next]=d[i][x]+1;
               if(!vis[next])
               {
                   vis[next]=1;
                   q.push(next);
               }
           }
       }
   }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
              if(i==j) d[i][j]=0;
              else d[i][j]=INF;
        }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        c[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        spfa(i);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(d[i][j]!=INF) a[i].push_back(make_pair(d[i][j],j));
            if(d[j][i]!=INF) b[i].push_back(make_pair(d[j][i],j));
        }
        sort(a[i].begin(),a[i].end());
        sort(b[i].begin(),b[i].end());
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int nn=b[i].size();
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
			if(d[i][j]==INF) continue;
            int mm=a[j].size();
            for(int k=nn-1;k>=0&&k>=nn-3;k--)
            {
                int kk=b[i][k].second;
                if(kk==j||kk==i) continue;
                for(int p=mm-1;p>=0&&p>=mm-3;p--)
                {
                    int pp=a[j][p].second;
                    if(pp==i||pp==j||pp==kk) continue;
                    if(ans<d[kk][i]+d[i][j]+d[j][pp])
                    {
                        ans=d[kk][i]+d[i][j]+d[j][pp];
                        res[1]=kk;res[2]=i;res[3]=j;res[4]=pp;
                    }
                }
            }
        }
    }
	//printf("%d\n",ans);
    for(int i=1;i<=4;i++)
    {
        if(i==4)
            printf("%d\n",res[i]);
        else
            printf("%d ",res[i]);
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-1276-Cash Machine(多重背包)

    Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

    ShenduCC
  • PAT 甲级 1003Emergency(Dijkstra最短路)

    1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...

    ShenduCC
  • POJ--1699 Best Sequence(DP+dfs)

    Best Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions...

    ShenduCC
  • 【Codeforces】1213B - Bad Prices

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • Uva----------(11078)Open Credit System

    Open Credit System Input:Standard Input Output: Standard Output In an open credi...

    Gxjun
  • hdu 2473 Junk-Mail Filter (并查集之点的删除)

    Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/...

    Gxjun
  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty
  • HDU 3032 Nim or not Nim?(Multi-Nim)

    Problem Description Nim is a two-player mathematic game of strategy in which ...

    attack
  • 【Codeforces】1220A - Cards

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • CF思维联系– Codeforces-988C Equal Sums (哈希)

    这个题,无论怎么循环都是超时的,所以必须想到一种不需要循环的方法,这里我用的是hash,因为是每个序列删掉一个之后相等,那我们就保存删掉一个数之后的值,用has...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券