这是一道最短路模板题，但是在理解题意和提出模型的阶段比较考验思维，很容易想到并且深深进入暴力拆解题目的无底洞当中。
题意是说：给出一个邻接矩阵，在每个点时，走且仅走向，合法路径中编号最小的点。问题是是否能够从0点走向n-1点。如果可以走到，求出，最少应当删除几个合法边（如果（1,2）（2,1）（2,3）同时合法，前两个边就会不停的循环，这时候必须删掉（2,1）才能够让（2,3）这条边被走到，从而到达新的节点）。
题解：重新定义变得权重：按照题意变得权重应当每次是1，但是显然在这道题的设定下，这个权重并没有意义。因此应当重新定义每条边的权重：使得邻接矩阵path[i][j]代表的含义是：如果要合法的走过这条边，应当删除前面的几条边？
普通的dijkstra：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 long long cases,n,m; 5 const long long MAXN=50+23; 6 const long long INF=1e12+233; 7 long long path[MAXN][MAXN]; 8 long long dp[MAXN]; 9 10 void init() 11 { 12 cin>>n; 13 for(int i=0;i<n;++i) 14 { 15 dp[i]=INF;long long point=0; 16 for(int j=0;j<n;++j) 17 { 18 path[i][j]=INF; 19 char c; 20 cin>>c; 21 22 if(c!='N') 23 { 24 path[i][j]=point; 25 point++; 26 } 27 } 28 } 29 } 30 bool v[MAXN]; 31 void dijkstra() 32 { 33 memset(v,0,sizeof(v)); 34 dp[0]=0;int x=0; 35 for(int i=0;i<n;++i) 36 { 37 long long mini=INF; 38 for(int j=0;j<n;++j) 39 { 40 if(!v[j]&&dp[j]<mini) 41 { 42 mini=dp[j]; 43 x=j; 44 } 45 }v[x]=1; 46 for(int j=0;j<n;++j) 47 { 48 dp[j]=min(dp[j],dp[x]+path[x][j]); 49 } 50 } 51 52 if(dp[n-1]==INF)cout<<"-1"<<endl; 53 else cout<<dp[n-1]<<endl; 54 } 55 56 int main() 57 { 58 cin.sync_with_stdio(false); 59 cin>>cases; 60 for(int itee=0;itee<cases;++itee) 61 { 62 init(); 63 dijkstra(); 64 } 65 return 0; 66 }
两行代码的解决方案：
1 #include<bits/stdc++.h> 2 using namespace std;long long cases,n,m;const long long MAXN=50+23;const long long INF=1e12+233;long long path[MAXN][MAXN];long long dp[MAXN];void init(){ cin>>n; for(int i=0;i<n;++i) { dp[i]=INF;long long point=0; for(int j=0;j<n;++j) { path[i][j]=INF; char c; cin>>c; if(c!='N') { path[i][j]=point; point++; } } }}bool v[MAXN];void dijkstra(){ memset(v,0,sizeof(v)); dp[0]=0;int x=0; for(int i=0;i<n;++i) { long long mini=INF; for(int j=0;j<n;++j) { if(!v[j]&&dp[j]<mini) { mini=dp[j]; x=j; } }v[x]=1; for(int j=0;j<n;++j) { dp[j]=min(dp[j],dp[x]+path[x][j]);}} if(dp[n-1]==INF)cout<<"-1"<<endl; else cout<<dp[n-1]<<endl;}int main(){ cin.sync_with_stdio(false); cin>>cases; for(int itee=0;itee<cases;++itee) { init(); dijkstra(); } return 0;}