dijk

//最短路径
/*


Dijkstra(迪杰斯特拉)算法的核心思想是贪心策略+动态规划
http://www.programgo.com/article/4721147659/
Dijkstra算法能得出最短路径的最优解，但是效率低
*/
#include <iostream>
using namespace std;
int main()
{
    int n,m,i,j,k,l,r;
    cin>>n>>m;

    int**s=new int*[n];//确定的是行数
    for(int i=0;i<n;i++)
    {
        s[i]=new int[n];//确定的是列数
    }
    //初始化，将自己与自己的距离置为0，任意两点距离置为99999
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
        {  if(i==j)  s[i][j]=0;
        s[i][j]=99999;
        }
    }

    //Input:
    for(k=0;k<m;k++)
    {
        cin>>i>>j;
        cin>>s[i][j];
    }

    /*dijkstra：
    主要特点是以起始点为中心向未碰到的点扩展，直到扩展到终点为止。
    */
    for (k=0; k<n; k++)
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                if (s[i][k] + s[k][j] < s[i][j])
                    s[i][j] = s[i][k] + s[k][j];
    cin>>l>>r;
    cout<<s[l][r];
    return 0;
}