公交线路

P市有n个公交站，之间连接着m条道路。P市计划新开设一条公交线路，该线路从城市的东站（s点）修建到西站（t点），请为P市设计一条满足上述条件并且最短的公交线路图。

Dijkstra求最短路

建立一个集合s，集合s是当前已经确定的、最短路的点

1.先初始化所有的点，起点为0，然后其它点都初始化为正无穷（第一步只有起点被遍历到）

2.接下来是一个循环的过程，循环n次，找到不在集合s中，距离最近的点（为t），把t加到s中去

3.用t更新所有点的距离——看dis[x]是否大于dis[t]+w(加上一个权重）

*每一个循环，都可以确定一个最短点的距离，循环n次就可以确定n个点的距离

*这样我们就可以求出每一个点到起点的最短距离了

*基于贪心

*时间复杂度O（n^3）

#include
#include<string.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int f[1020][1020];
 
int main()
{
    int n, m, s, t;
    int  x,y,z;
    cin >> n >> m >> s >> t;
    memset(f,inf,sizeof(f));
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        f[x][y] = min(f[x][y], z);
        f[y][x] = min(f[y][x], z);
    }
 
    for (int i = 1; i <= n; i++)
    {
        f[i][i] = 0;
    }
 
    for (int p = 1; p <= n; p++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] = min(f[i][j], f[i][p] + f[p][j]);
 
    if (f[s][t] >= inf)
        cout << -1 << endl;
    else
        cout << f[s][t] << endl;
    return 0;
 
}