最短路上机【dijkstra】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f3f

int path[105];
int ma[105][105];
bool vis[105];
int dis[105];
int n,m;

void init(){
    cin>>n>>m;//n边 m点
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(i==j) ma[i][j]=0;
            else ma[i][j]=inf;
        }
    }
    int x,y,v;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>v;
        ma[x][y]=v;
        ma[y][x]=v;
    }
    memset(vis,0,sizeof(vis));
}

void show(){
    cout<<"----------------------------"<<endl;
    cout<<"矩阵："<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            printf("%-20d",ma[i][j]);
        }
        puts("");
    }
    cout<<"----------------------------"<<endl;
}

int main(){
    init();
    show();
    int st,en,temp;
    cout<<"输入起点和终点:"<<endl;
    cin>>st>>en;
    cout<<"----------------------------"<<endl;
    for(int i=1;i<=m;i++){
        dis[i]=ma[st][i];
        if(dis[i]<inf) path[i]=st;
        else path[i]=-1;
    }
    vis[st]=1;
    for(int i=1;i<=m-1;i++){
        int _min=inf;
        for(int j=1;j<=m;j++){
            if(vis[j]==0 && dis[j]<_min){
                _min=dis[j];
                temp=j;
            }
        }
        vis[temp]=1;
        for(int k=1;k<=m;k++){
            if(ma[temp][k]<inf && dis[temp]+ma[temp][k]<dis[k]){
                dis[k]=dis[temp]+ma[temp][k];
                path[k]=temp;
            }
        }
    }
    cout<<"最短路径长度是:"<<endl<<dis[en]<<endl;
    cout<<"----------------------------"<<endl;
    cout<<"打印最短路径是:"<<endl;
    int t=en;
    cout<<en<<"->";
    while(path[t]!=st){
        cout<<path[t]<<"->";
        t=path[t];
    }
    cout<<st<<endl;
    cout<<"----------------------------"<<endl;
    return 0;
}
/*
9 6
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
input 1 5
ouput 13
*/