课设校园导航系统，堆优化dijkstra+DFS
本废物的第一次实训，本以为很简单的两个算法，在实际较为接近工程的场景中竟然耗费了较长时间，但经过数天思考后，是用最简单的写法勉强实现，但没有将数字转变为其代表的地点名，供大家参考批评（大二打不上比赛的废物呜呜呜）
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=30;
const int M=1e6+10;
int g[N][N];
bool st[N];//判断是否已经在最短路集合中
bool flag[N];
int dist[N];
int n=25;
int num=1000000000;//用于dfs中比较并选出最小权值
long long q[M],l=0;
int zdl[M],res=0;//记录最短路及点数
typedef pair<int,int> PII;//到起点的最短距离，编号；由于pair优先以first排序，故不可以first为编号
priority_queue<PII,vector<PII>,greater<PII> > heap;//定义小根堆
int dijkstra(int l,int r)
{
memset(dist,0x3f,sizeof dist);
dist[l]=0;//初始化源点坐标
heap.push({0,l});
while(heap.size()) //堆中不为空，最多有m个点（m为边数量）
{
PII t=heap.top();
heap.pop();
int ver=t.second;//点编号
int d=t.first;//点到起点距离
if(st[ver]==true)continue;//堆中会有冗余点，需要跳过
st[ver]=true;//加入集合，可省略，但会影响时间性能
for(int i=1;i<=n;i++)
{
int j;
if(g[ver][i]<100000&&!st[i])j=i;//在矩阵中找到邻接点
if(dist[j]>d+g[ver][j])//可更新到起点的最短距离
{
dist[j]=d+g[ver][j];
heap.push({dist[j],j});
}
}
}
if(dist[r]==0x3f)return -1;
else return dist[r];
}
bool check()
{
for(int i=1;i<=n;i++)if(flag[i]==true)return false;//flag为true代表必经点还没有走到
return true;
}
void dfs(int u,int ans,int end)
{
if(u==end)
{
if(check())//当且仅当走到终点且所有必经点都走到时进行返回
{
if(ans<num)
{
memset(zdl,0,sizeof zdl);
for(int i=0;i<l;i++)zdl[i]=q[i];
}
num=min(ans,num);
for(int i=0;i<l-1;i++)cout<<q[i]<<"->";
cout<<q[l-1]<<"该路径总路程为"<<ans<<endl;
}
return ;
}
st[u]=true;
//u为当前走到的点
for(int i=1;i<=n;i++)
{
if(g[u][i]<100000&&st[i]==false)//u、i之间存在边且尚未走过
{
q[l++]=i;
ans+=g[u][i];
bool x=flag[i];
if(x==true)flag[i]=false;
//在递归调用之前做一些检查或者其他操作
dfs(i,ans,end);
//确保在递归调用结束后，立即进行状态还原
if(x==true)flag[i]=true;
ans-=g[u][i];
l--;
}
}
st[u]=false;
}
int main()
{
memset(g,0x3f,sizeof g);
g[1][24]=635;
g[1][3]=415;
g[1][2]=430;
g[1][16]=530;
g[2][1]=430;
g[2][4]=230;
g[2][12]=350;
g[2][7]=357;
g[2][21]=520;
g[3][4]=20;
g[4][5]=20;
g[5][12]=78;
g[6][7]=20;
g[6][12]=78;
g[7][8]=20;
g[8][21]=100;
g[9][24]=90;
g[9][14]=350;
g[9][10]=80;
g[9][11]=400;
g[10][25]=200;
g[11][25]=40;
g[14][20]=220;
g[14][16]=240;
g[15][17]=200;
g[15][18]=100;
g[15][22]=185;
g[15][23]=190;
g[16][1]=530;
g[16][20]=80;
g[22][23]=120;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(g[i][j]>10000000)g[i][j]=g[j][i];
puts("1.综合楼到终点最短路径");
puts("2.任意两点最短路径");
puts("3.经过必经点的最短路径");
printf("请您选择：");
int x;
cin>>x;
if(x==1)
{
int l,r;//最短路起点与终点
l=1;
printf("请输入终点：");
cin>>r;
cout<<dijkstra(l,r);
memset(dist,0,sizeof dist);//复原
memset(st,false,sizeof st); //复原
}
else if(x==2)
{
int l,r;//最短路起点与终点
printf("请输入起点与终点：");
cin>>l>>r;
cout<<dijkstra(l,r);
memset(dist,0,sizeof dist);//复原
memset(st,false,sizeof st); //复原
}
else
{
printf("请输入起点与终点：");
int fl,fr;//起点 终点
cin>>fl>>fr;
q[l++]=fl;
printf("请输入您的必经点：");
getchar();//在上一次输入完成后按下回车，若不加getchar按下的回车会直接作为字符输入下面循环，导致无法输入
char s;
int a;
while(scanf("%c",&s)&&s!='\n')
{
if(s==' ')//若为这种情况则输入一个数字时也要加一个空格
{
flag[a]=true;
//cout<<a<<endl;
a=0;
continue;
}
int x=s-'0';
a=a*10+x;
}
if(a>0)flag[a]=true;
dfs(fl,0,fr);//起点，总权值，终点
printf("最短路径为：");
int i=0;
while(zdl[i+1]!=0)
{
cout<<zdl[i]<<"->";
i++;
}
cout<<zdl[i]<<endl;
printf("最短路径长度为：");
cout<<num<<endl;
}
return 0;
}
print('Hello world!')
投递京东等公司10个岗位
