zufeoj_最短路径迪杰斯特拉算法入门

题目链接：http://acm.ocrosoft.com/problem.php?cid=1172&pid=60

题目描述

如图，求最短路径。

输入

顶点数n 边数m

m条边的顶点和权值

某两个顶点

输出

顶点0到每个顶点的最短路径

样例输入

6 9
0 2 5
0 3 30
1 0 2
1 4 8
2 1 15
2 5 7
4 3 4
5 3 10
5 4 18
0 4

样例输出

28

#include<bits/stdc++.h>
using namespace std;
int u,v,w;
int n,m;
int st,en;
int e[111][111],dis[111],vis[111];
const int inf=9999999;
void Dijkstra(int st,int en){
    int u,v;
    for(int i=0;i<n;i++){
        dis[i]=e[st][i];
    }
    dis[st]=0;
    vis[st]=1;
    int minn;
    for(int i=0;i<n-1;i++){
        minn=inf;
        for(int j=0;j<n;j++){
            if(vis[j]==0&&dis[j]<minn){
                minn=dis[j];
                u=j;
            }
        }
        if(minn==inf)
        break;
        vis[u]=1;
        for(v=0;v<n;v++){
            if(e[u][v]<inf){
                if(vis[v]==0&&dis[v]>dis[u]+e[u][v]){
                    dis[v]=dis[u]+e[u][v];
                }
            }
        }
    }
    cout<<dis[en]<<endl;
}
int main(){
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                e[i][j]=0;
            }else{
                e[i][j]=inf;
            }
        }
    }
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        e[u][v]=w;
    }
    cin>>st>>en;
    Dijkstra(st,en);    
    return 0;
}