题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

平均 O(m) 最坏O(nm)

参考文献

spfa 求最短路可以用宽搜理解； 首先初始化dist数组，所有点不可达，然后更新d[1]=0;把1放入队列；while队列不空；取出队头，遍历队头可以到达的顶点j；如果距离d[j]变小就更新；如果j不在队列就放进去（在的话就不用放，不然会重复枚举）；

C++ 代码

blablabla

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], w[N], ne[N], idx, n, m;
int d[N];
bool st[N];

void add(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;

}


int spfa()
{
    memset(d, 0x3f, sizeof d);    //首先初始化dist数组，所有点不可达，然后更新d[1]=0;
    d[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;                 //1已经进队列

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;  //同一个点可以进队列多次；
        for(int i = h[t]; i != -1; i = ne[i])    //只会更新 源点可以到达的点； 所以只用判断d[n] ==                                                                                        //0x3f3f3f3f
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }

            }
        }

    }


}


int main()
{
    cin>> n >> m;

    memset(h, -1, sizeof h);
    int x, y, z;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);               //重边不影响结果，都存进去不影响

    }

    int t = spfa();

    if(t == 0x3f3f3f3f) cout<< "impossible";
    else cout<< t;
    return 0;
}