输入：
第一行输入n（表示n个节点）m（表示m条边）
此后m行，每行三个数，第一个数表示出发结点，第二个数表示到达的结点，第三个数表示边权
输出：
输出一个数，表示从结点1出发到结点n的最短路径（若无法到达则输出Unable to reach）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,map1[110][110],m1[110],min1; //n代表节点数，m代表边数，map1代表矩阵也表示从i到j有无路径，有的话里程是多少，m1代表是否访问过，min1代表最小里程 void dfs(int i,int luj){ if(luj>min1)return ; //luj代表的是当前已经走过的里程，若大于已知最小里程则没必要进行下边的 if(i==n){ //若到达最终点则判断里程是否小于已知最小里程，若小于则更新最小里程 if(min1>luj)min1=luj; return ; } else{ int j; for(j=1;j<=n;j++){ if(m1[j]==0&&map1[i][j]!=999999999&&map1[i][j]!=0){//若从i点出发到j点由路径且没有访问过则使用递归访问 m1[j]=1; dfs(j,luj+map1[i][j]); m1[i]=0; } } return; } } int main(){ cin>>n>>m; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ map1[i][j]=999999999; } map1[i][i]=0; } for(int i=0;i<m;i++){ int u,o,p; cin>>u>>o>>p; map1[u][o]=p; //此为有向图，单向可行，若为无向图则更改为 map1[u][o]=p;map1[o][u]=p; } memset(m1,0,sizeof(m1)); min1=999999999; m1[1]=1; dfs(1,0); if(min1!=999999999)cout<<min1<<endl; else cout<<"Unable to reach"<<endl; return 0; }