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 分)