PAT 1163 Dijkstra Sequence(30)
题目
代码
参考代码
// 相等的时候有多种取法, 逐一判断
#include<bits/stdc++.h>
using namespace std;
int inf = 0x7f7f7f7f;
int edge[1100][1100];
int dist[1100];
bool visit[1100];
int main() {
fill(edge[0], edge[0] + 1100 * 1100, inf);
int nv, ne;
cin >> nv >> ne;
for(int i = 0; i < ne; i++) {
int a, b, weight;
cin >> a >> b >> weight;
edge[a][b] = edge[b][a] = weight;
}
//cout << edge[3][4] << endl;
// 开始判断
int k;
cin >> k;
for(int i = 0; i < k; i++) {
// 记录一下待判断的seq
vector<int> v(nv);
// 存一下
for(int j = 0; j < nv; j++)
cin >> v[j];
//cout << v[0] << endl;
// 开始判断
// 初始化dist, visit
fill(dist, dist + 1100, inf);
fill(visit, visit + 1100, false);
// 起始点
dist[v[0]] = 0;
// 依次检查
bool flag = true;
for(int j = 0; j < nv; j++) {
// 寻找最小的dist, 判断是否符合
int minn = inf;
vector<int> record;
for(int k = 1; k <= nv; k++) {
if(visit[k] == false) {
if(dist[k] == minn) record.push_back(k);
else if(dist[k] < minn) {
minn = dist[k];
record.clear();
record.push_back(k);
}
}
}
int checkpoint = -1;
/*
for(int k = 0; k < record.size(); k++) cout << record[k] << " ";
cout << endl;
*/
for(int k = 0; k < record.size(); k++) {
if(record[k] == v[j]) {
checkpoint = k;
break;
}
}
// 看看能不能找到
if(checkpoint == -1) {
flag = false;
break;
}
// 如果可以找到
int u = v[j];
visit[u] = true;
// 后面更新dist
for(int v = 1; v <= nv; v++) {
if(visit[v] == false) {
if(dist[v] > dist[u] + edge[u][v]) dist[v] = dist[u] + edge[u][v];
}
}
}
if(flag == false)
cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
}
复现代码
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int vis[1005],dis[1005],edge[1005][1005];
int main()
{
memset(edge,inf,sizeof(edge));
int nv,ne;
cin>>nv>>ne;
while(ne--){
int x,y,z;
cin>>x>>y>>z;
edge[x][y]=edge[y][x]=z;
}
int cnt;
cin>>cnt;
while(cnt--){
vector<int> v(nv);
for(int i=0;i<nv;i++){
cin>>v[i];
}
fill(dis,dis+1005,inf);
fill(vis,vis+1005,0);
dis[v[0]]=0;//注意顺序
int flag=1;
for(int t=0;t<nv;t++){
int minn=inf;
vector<int> point;
for(int i=0;i<nv;i++){
if(!vis[v[i]]){
if(dis[v[i]]<minn){
minn=dis[v[i]];
point.clear();
point.push_back(v[i]);
}
else if(dis[v[i]]==minn){
point.push_back(v[i]);
}
}
}
int check=-1;
for(int i=0;i<point.size();i++){
if(point[i]==v[t]){
check=point[i];
}
}
if(check==-1){
flag=0;
break;
}
int u=v[t];
vis[u]=1;
for(int v=1;v<=nv;v++){
if(!vis[v]&&dis[u]+edge[u][v]<dis[v]){
dis[v]=dis[u]+edge[u][v];
}
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
参考文章
pat甲级:1163 Dijkstra Sequence (30 分)
注意
复现时,遇到了很多问题,导致无法一遍成功,现将我自己遇到的问题分享给大家
1
fill(f[0],f[0]+1005*1005,inf);
问题:错把inf误写为0
分析:之所以是inf,是因为inf代表一开始两两互不相连
2
vector<int> point;
问题:错将这行代码放在for(int t=0;t<n;t++)
之外
分析:t代表更新的轮次,也可以理解为输入序列的对应位置。point是在每次更新后要重置,因此必须放在t循环内部
3
for(int i=1;i<=n;i++)
问题:i<=n的等号忘写了
分析:这里的i直接代表点,而不是数组的位置,之所以这么写是为了图方便(不想写v[i]),但很容易出错,要十分注意