题目描述
明明同学被困在一个荒凉的北极岛屿，他可以用小船乘着海流用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的小伙伴可以通过以下的链接来进行学习~~（巨佬请忽略）~~
方法一
#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"); }
以上便是对本题的相关阐述
