題目背景

輸入

輸出

完整代碼

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1010],dist[1010],g[1010][1010],st[1010];int dij(int u){memset(st,0,sizeof st);memset(dist,0x3f,sizeof dist);dist[u]=0;for(int i=0;i<n;i++){int t=a[i];for(int j=1;j<=n;j++){if(!st[j]&&dist[j]<dist[t]) return 0;}for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);}st[t] = 1;}return 1;
}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int v,w,r;cin>>v>>w>>r;g[v][w]=g[w][v]=min(g[v][w],r);}cin>>k;for(int i=0;i<k;i++){for(int i=0;i<n;i++) cin>>a[i];cout<<(dij(a[0])?"Yes":"No")<<"\n";}return 0;
}

---

這道題就是看每次dij方法和他給的點是不是一樣近。
dij方法好像都是開那幾個數組，dij函數一樣，大概也就鄰接表 鄰接矩陣 堆優化幾種吧。