课设校园导航系统，堆优化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!')