UPC训练第23场——寻路——弗洛伊德

简介: 题目描述明明同学被困在一个荒凉的北极岛屿,他可以用小船乘着海流用1单位时间从一个岛移动到另一个岛。他得到了一个海洋地图,有N(1<=N<=100)条单向海流航线,编号为1…N。告诉你他的起始位置M(1<=M<=N)和地图,请编程帮助明明确定到达每个岛的最短时间是多少。输入为一个矩阵C,第r行,第c列的值若为1,则r到c存在海流,值为0则不存在海流。

题目描述


明明同学被困在一个荒凉的北极岛屿,他可以用小船乘着海流用1单位时间从一个岛移动到另一个岛。他得到了一个海洋地图,有N(1<=N<=100)条单向海流航线,编号为1…N。

告诉你他的起始位置M(1<=M<=N)和地图,请编程帮助明明确定到达每个岛的最短时间是多少。

输入为一个 矩阵 C,第r行,第c列的值若为1,则r到c存在海流,值为0则不存在海流。


输入


第1行:两个用空格隔开的整数:N和M

第2…N+1:第i+1行包含N个用空格隔开的整数:C_R


输出


第1…??行:第一行输出M,第i+1行包含时刻i能到达的岛屿(升序排列)


样例输入


4 1 
0 1 0 1 
0 0 1 0 
0 0 0 1 
0 0 0 0


样例输出


1
2 4
3


当时做这个题的时候,可以感觉出考点是弗洛伊德全源最短路问题,但是死活没明白样例是什么意思,于是乎卡了好像时间,先介绍一下题目的意思叭。


给出的矩阵表达的意思是如果第 i 行,第 j 列是1,那么说明可以从 i 到达 j 。如果是0的话,那么就说明无法从 i 到 j 。 而给出的起点 m 可以看做是第几行的开始。拿样例来说,1,2为1,说明可以从1->2; 1,4为1,可以说明可以从1->4,两个需要的时间都是 1 。而要是从1->3 那么来说需要从1->2,2->3,两步来完成,耗时为2(样例第二行可以看出能够从2->3).

输出情况就是先输出耗时短可以到达的岛屿,往下是耗时比较长的岛屿,如果好耗时相同,那么来说就需要从编号从小到大进行输出,比如耗时为1的可以从1到达的岛屿有24,先输出2,在输出4.


下面将附上本人的两种方法,两种方法都是可行的(根本都是一样的就只是用的vector方式不太一样罢了),但是之前一种方法因为一个条件把自己卡的死死的。伤心

想要很好了解vector的小伙伴可以通过以下的链接来进行学习~~(巨佬请忽略)~~


传送门1


传送门2


传送门3


方法一


#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const ll INF = 0x3f3f3f3f;
const int maxn = 2e6 + 7;
const int mod = 1e9 + 7;
ll maxx=-1;
ll minn=inf;
ll num[1008];
ll dis[1008][1008];
ll num2[maxn];
ll res,ans;
map<string,ll> mp;
priority_queue <int ,vector<int> ,greater<int> > xiaogen;
bool cmp(ll a,ll b){
    return a>b;
}
queue <ll> duilie;
queue <ll> cnt;
vector <ll> vet;
int main()
{
    int n=read,m=read;
    for(int i=1;i<=n;i++){///初始化操作,将从自己到自己的时间设置成0
        for(int j=1;j<=n;j++){
            if(i==j) dis[i][j]=0;
            else dis[i][j]=mod;///其余设置成比较大的模数
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a=read;
            if(a==0) continue;/// 如果是0那就说明两点不同就不再理会直接跳过
            else if(a==1) dis[i][j]=1;
        }
        dis[i][i]=0;///为了保险还是要将这里改成0,数据没问题应给可以不用加,但是本蒟蒻没有尝试
    }
    for(int k=1;k<=n;k++){/// 弗洛伊德三层for
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    /// 按照题目要求进行输出
    cout<<m<<endl;
    for(int i=1;i<=n;i++){
            ll temp=dis[m][i];
            num[i]=temp;
            if(temp==mod) temp=0;/// 划重点!91%卡在了这里
            vet.push_back(temp);
    }
    /// 排序去重
    sort(vet.begin(),vet.end());
    vet.erase(unique(vet.begin(),vet.end()),vet.end());
    int len=vet.size();/// 检测vector中存放了多少个数
    for(int i=1;i<=len-1;i++){
        for(int j=1;j<=n;j++){
            if(vet[i]==num[j]){///对应相等输出对应的编号
                printf("%d ",j);
            }
        }
        puts("");
    }
    return 0;
}


warning


  for(int i=1;i<=n;i++){
            ll temp=dis[m][i];
            num[i]=temp;
            if(temp==mod) temp=0;/// 划重点!91%卡在了这里
            vet.push_back(temp);
    }


在这里如果两点行不通的情况下不排除,将会卡在91%,亲测有效

在这里本蒟蒻优化了一下,将行不通的情况那个临时变量temp 变成0,这样一来就会将和自身到自身的那个0在后面去重掉,将不影响最终结果


方法2


#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const ll INF = 0x3f3f3f3f;
const int maxn = 2e6 + 7;
const int mod = 1e9 + 7;
ll maxx=-1;
ll minn=inf;
ll num[1008];
ll dis[1008][1008];
ll num2[maxn];
ll res,ans;
map<string,ll> mp;
priority_queue <int ,vector<int> ,greater<int> > xiaogen;
bool cmp(ll a,ll b){
    return a>b;
}
queue <ll> duilie;
queue <ll> cnt;
vector <ll> vet[maxn];
int main()
{
    int n=read,m=read;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) dis[i][j]=0;
            else dis[i][j]=mod;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a=read;
            if(a==0) continue;
            else if(a==1&&i!=j) dis[i][j]=1;
        }
        dis[i][i]=0;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    cout<<m<<endl;
    for(int i=1;i<=n;i++){
        if(i!=m&&dis[m][i]!=mod){
            ll temp=dis[m][i];
            maxx=max(maxx,temp);
            vet[temp].push_back(i);
        }
    }
    for(int i=1;i<=maxx;i++){
        for(auto tmp:vet[i]) cout<<tmp<<" ";
        printf("\n");
    }
    return 0;
}


和第一种方式不同的只有这一点,但是第一次使用这种方式过的,不容易忘记条件,但是说实话,本蒟蒻驾驭不了这种使用vector的方式,看的到这种方法真的是眼前一亮


  /// 前面声明的时候一定要记得加上想要申请的vector的大小
  /// 例如: vector <ll> vet[maxn];
    cout<<m<<endl;
    for(int i=1;i<=n;i++){
        if(i!=m&&dis[m][i]!=mod){
            ll temp=dis[m][i];
            maxx=max(maxx,temp);
            vet[temp].push_back(i);
        }
    }
    for(int i=1;i<=maxx;i++){
        for(auto tmp:vet[i]) cout<<tmp<<" ";
        printf("\n");
    }


以上便是对本题的相关阐述

目录
相关文章
|
1月前
|
传感器 编解码 人工智能
中科星图——MCD43A4 V6天底双向反射率分布函数调整反射率(NBAR)数据集
中科星图——MCD43A4 V6天底双向反射率分布函数调整反射率(NBAR)数据集
118 8
|
1月前
|
机器学习/深度学习 算法 数据挖掘
Hybrid-SORT起飞 | 超过DeepSORT将近10个点的多目标跟踪香不香?
Hybrid-SORT起飞 | 超过DeepSORT将近10个点的多目标跟踪香不香?
105 0
|
1月前
|
机器学习/深度学习 固态存储 算法
目标检测的福音 | 如果特征融合还用FPN/PAFPN?YOLOX+GFPN融合直接起飞,再涨2个点
目标检测的福音 | 如果特征融合还用FPN/PAFPN?YOLOX+GFPN融合直接起飞,再涨2个点
143 0
|
11月前
|
机器学习/深度学习
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
62 0
|
1月前
|
机器学习/深度学习 算法 计算机视觉
【论文速递】CVPR2021 - 基于自引导和交叉引导的小样本分割算法
【论文速递】CVPR2021 - 基于自引导和交叉引导的小样本分割算法
28 0
|
机器学习/深度学习 人工智能 自然语言处理
中山大学团队使用端到端图生成架构进行分子图编辑的逆合成预测
中山大学团队使用端到端图生成架构进行分子图编辑的逆合成预测
136 0
|
机器学习/深度学习 存储 并行计算
神经辐射场去掉「神经」,训练速度提升100多倍,3D效果质量不减
神经辐射场去掉「神经」,训练速度提升100多倍,3D效果质量不减
122 0
|
算法 数据挖掘
秒懂算法 | 基于K-Means算法的汽车行驶运动学片段的分类
汽车在行进过程中会产生连续的一组数据,包含加速度,速度等参数,汽车形式运动学片段是指是从一个怠速开始到下一个怠速开始之间的运动行程,通常包括一个怠速部分和一个行驶部分。而怠速指的是汽车停止运动,但发动机保持最低转速运转的连续过程。行驶部分通常包含加速、巡航和减速三种运动模式。
247 0
秒懂算法 | 基于K-Means算法的汽车行驶运动学片段的分类
|
人工智能
UPC——2020年春混合个人训练第二十四场(DEFG)
UPC——2020年春混合个人训练第二十四场(DEFG)
88 0
UPC——2020年春混合个人训练第二十四场(DEFG)
|
人工智能 定位技术 Go
UPC——2020年春混合个人训练第二十五场(FG)
UPC——2020年春混合个人训练第二十五场(FG)
69 0

热门文章

最新文章