[蓝桥杯 2022 国 B] 出差（迪杰斯特拉）

该题非常明显是一道关于最短路径的问题，这里我想的第一个思路是使用floyd（因为容易），当然O(n^3)无法满足该题要求的时间复杂度 #include<iostream> #include<climits> #define MAX 1010 using namespace std; int mapp[MAX][MAX]; int main(){ int n,m; cin>>n>>m; int C[MAX]; for(int i=0;i<n;i++){ cin>>C[i]; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ mapp[i][j]=100000; } } for(int i=0;i<m;i++){ int u,v,c; cin>>u>>v>>c; mapp[u-1][v-1]=c; } for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j)continue; if(mapp[i][k]+mapp[k][j]+C[k]<mapp[i][j]){ mapp[i][j]=mapp[i][k]+mapp[k][j]+C[k]; } } } } cout<<mapp[0][n-1]<<endl; return 0; }

最好的做法还是使用迪杰斯特拉算法进行解答（下面只是使用朴素的迪杰斯特拉即可解决该问题） #include<iostream> #include<climits> #include<algorithm> #define MAX 1010 using namespace std; int mapp[MAX][MAX]; int C[MAX]; int dis[MAX]; bool flag[MAX];//标记下标为i的点是否已经找到最短路径 int main(){ int n,m; cin>>n>>m; for(int i=0;i<n;i++){ cin>>C[i]; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ mapp[i][j]=999999; } } for(int i=0;i<m;i++){ int u,v,c; cin>>u>>v>>c; mapp[u-1][v-1]=c+C[v-1]; mapp[v-1][u-1]=c+C[u-1]; } for(int i=0;i<n;i++){ dis[i]=999999;//初始化 } dis[0]=0;//初始化起点到起点 for(int i=0;i<n;i++){ int temp=-1; for(int j=0;j<n;j++){//找到距离最短的点 if(!flag[j]&&(temp==-1||dis[j]<dis[temp])){ temp=j; } } flag[temp]=true;//标记已经找到最短路径 for(int j=0;j<n;j++){//根据t点更新其他点的最短路径 dis[j]=min(dis[j],dis[temp]+mapp[temp][j]); } } cout<<dis[n-1]-C[n-1]<<endl;//注意终点无需隔离 return 0; }