最短路C++蓝桥杯

题目描述

本题为填空题&＃xff0c;只需要算出结果后&＃xff0c;在代码中使用输出语句将所填结果输出即可。

如下图所示&＃xff0c;G 是一个无向图&＃xff0c;其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。则从 AA 到 SS 的最短距离是多少&＃xff1f;

运行限制
最大运行时间&＃xff1a;1s
最大运行内存: 128M

最短路径模板题&＃xff0c;初始化比较麻烦&＃xff0c;一共36条路径。

我初始化的时候A-S分别用1-19代替。初始化的时候保证从一个小的数字出发到一个大一点的数字。这样就不会重复了。

#include
using namespace std;
#define lnf 0x7FFFFFFF
int dis[25],vis[25];
int imap[25][25];
void iset(int x,int y,int num){imap[x][y]&＃61;imap[y][x]&＃61;num;cout<<imap[x][y]<<endl;
}
void intial(){iset(1,5,1);iset(1,4,1);iset(1,3,1);iset(1,2,2);iset(2,7,1);iset(2,10,2);iset(3,4,3);iset(3,7,3);iset(3,6,3);iset(4,5,1);iset(4,9,2);iset(4,8,1);iset(4,7,2);iset(5,9,3);iset(5,8,1);iset(6,7,1);iset(6,10,1);iset(7,9,3);iset(7,11,2);iset(8,9,1);iset(8,12,2);iset(9,13,3);iset(10,19,2);iset(11,12,3);iset(11,16,2);iset(11,14,1);iset(12,13,1);iset(12,18,1);iset(13,19,1);iset(13,17,1);iset(13,14,2);iset(14,16,1);iset(15,17,1);iset(15,18,3);iset(15,16,1);iset(18,19,1);
}
int main()
{for(int i&＃61;1;i<&＃61;25;i&＃43;&＃43;){vis[i]&＃61;1;dis[i]&＃61;lnf;for(int j&＃61;1;j<&＃61;25;j&＃43;&＃43;)imap[i][j]&＃61;lnf;}intial();int s&＃61;1;int t&＃61;19;dis[s]&＃61;0;vis[s]&＃61;0;int imin;int inext;for(int i&＃61;1;i<&＃61;19;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;18;j&＃43;&＃43;){cout<<imap[i][j]<<" ";}cout<<endl;}while(s!&＃61;t){imin&＃61;lnf;for(int i&＃61;1;i<&＃61;19;i&＃43;&＃43;){if(imap[s][i]!&＃61;lnf)dis[i]&＃61;min(dis[i],dis[s]&＃43;imap[s][i]);if(vis[i]&&dis[i]<imin){imin&＃61;dis[i];inext&＃61;i;}}if(imin&＃61;&＃61;lnf)break;s&＃61;inext;vis[s]&＃61;0;}cout<<endl;for(int i&＃61;1;i<&＃61;19;i&＃43;&＃43;)cout<<dis[i]<<" ";cout<<endl;cout<<dis[t]<<endl;return 0;
}