【小岛】洛谷P2683

最短路模板题，如果对最短路不是很熟悉的同学请移步：
传送门

进入正题

此题与其他题不同的是，每新增条边，就必须存储，然后等1操作到达时跑最短路，于是我们有dijkstra和SPFA两种跑最短路的方法：

其次，如何处理无法到达呢。只需要if(dis[]==inf)就行了。

因为我们dis一开始初始化为inf，如果在接下来的跑最短路中没有被更新（也就是dis==inf），说明由当前起点是到不了这个点的。

dinjkstra:

dijkstra的核心就在于它的算法步骤：

算法步骤:
1. 找离起点x最近的未讨论过的点k。
2. 判断经过k点，起点x到其他点的距离是否缩短，如缩短
则更新。将k点标记为已讨论。
3. 重复进行第1步，直到所有点都被讨论过为止。

所以dijkstra的实质是贪心，但是在上述步骤1中，我们可以使用强大的stl中的优先队列来快速查找。

所以dijkstra的时间复杂度为 $O(nlog_n)$

$code$ :

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10005;
const ll inf=1e15;
struct node{    重载运算符，将dis关键字从小到大排序
    int num;
    ll dis;
    bool operator < (const node &a) const{
        return dis>a.dis;
    }
};
int n,m;
ll dis[N];
bool mark[N];
int Last[N],End[N],len[N],Next[N],tot;
void cb(int x,int y,int z){
    End[++tot]=y;
    len[tot]=z;
    Next[tot]=Last[x];
    Last[x]=tot;
}
void dijkstra(int s){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        mark[i]=false;
    }
    dis[s]=0;
    //mark[s]=true;
    priority_queue<node> q;       以dis作为关键字的小根堆
    q.push((node){s,0});
    while(q.size()){
        int u=q.top().num;     取出距离起点最近的点
        q.pop();
        if(mark[u])
            continue;
        mark[u]=true;
        for(int i=Last[u];i;i=Next[i]){   链式前向星
            int v=End[i];
            if(!mark[v] && dis[v]>dis[u]+len[i]){  更新最短距离
                dis[v]=dis[u]+len[i];
                q.push((node){v,dis[v]});
            }
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int opt,x,y,z;
        scanf("%d",&opt);
        if(opt){   opt==1 记录边
            scanf("%d %d %d",&x,&y,&z);
            cb(x,y,z);
            cb(y,x,z);
        }
        else{
            scanf("%d %d",&x,&y);
            dijkstra(x);     跑最短路
            if(dis[y]!=inf)   判断是否可以到达
                printf("%lld\n",dis[y]);
            else
                puts("-1");
        }
    }
    return 0;
}

SPFA(bellman-ford)

算法流程:

用一个队列来进行维护。初始时将起点加入队列。

每次从队列中取出一个元素，并对他所连接的点进行松弛，若某个点松弛成功（则通过那个点到起点距离缩短），则将其入队。直到队列为空

简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点

SPFA的时间复杂度是O(kE)，k一般取2左右（k是增长很快的函数ackermann的反函数,2^65536次方也就5以下），可以处理负边。

$code$ :(其实跟dijkstra差不多）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10005;
const ll inf=1e15;
int n,m;
ll dis[N];
bool mark[N];
int Last[N],End[N],len[N],Next[N],tot;
void cb(int x,int y,int z){
    End[++tot]=y;
    len[tot]=z;
    Next[tot]=Last[x];
    Last[x]=tot;
}
void spfa(int s){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        mark[i]=false;
    }
    dis[s]=0;
    mark[s]=true;
    queue<int> q;
    q.push(s);
    while(q.size()){
        int u=q.front();
        q.pop();
        mark[u]=false;
        for(int i=Last[u];i;i=Next[i]){
            int v=End[i];
            if(dis[v]>dis[u]+len[i]){
                dis[v]=dis[u]+len[i];
                if(!mark[v]){
                    q.push(v);
                    mark[v]=true;
                }
            }
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int opt,x,y,z;
        scanf("%d",&opt);
        if(opt){
            scanf("%d %d %d",&x,&y,&z);
            cb(x,y,z);
            cb(y,x,z);
        }
        else{
            scanf("%d %d",&x,&y);
            spfa(x);
            if(dis[y]!=inf)
                printf("%lld\n",dis[y]);
            else
                puts("-1");
        }
    }
    return 0;
}