图论——最短路径迪杰斯特拉算法入门

问题 G: 最短路径迪杰斯特拉算法入门

时间限制: 1 Sec  内存限制: 128 MB
提交: 190  解决: 169
[提交][状态][讨论版][命题人:quanxing]

题目描述

如图，求最短路径。

输入

顶点数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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a,b,k,x,y; 
int map[101][101],visit[101],low[101];
void dijstra()
{
    int temp;
    int k;
    memset(visit,0,sizeof(visit));
    visit[x]=1;
    for(int i=0;i<n;i++)
    low[i]=map[x][i];
    for(int i=0;i<n;i++)
    {
        temp=inf;
        for(int j=0;j<n;j++)
        if(!visit[j]&&temp>low[j])temp=low[j],k=j;
        visit[k]=1;
        for(int j=0;j<n;j++)
        if(!visit[j]&&map[k][j]+low[k]<low[j])
        low[j]=map[k][j]+low[k];
    }
}
int main()
{
   memset(map,inf,sizeof(map));
   cin>>n>>m;
   for(int i=0;i<n;i++)
   map[i][i]=0;
   for(int i=0;i<m;i++)
   {
        cin>>a>>b>>k;
        map[a][b]=k;
   }
   cin>>x>>y;
   dijstra();
   cout<<low[y];
    return 0;
}