Floyd-85分，超时。
Dij-过。

#include <iostream>
#include <cstring>

using namespace std;

unsigned int dis[101][101];
int n,m;

void floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}

void out(int i,int j)
{
    if(dis[i][j]<1e9)
    {
        cout<<dis[i][j]<<endl;
    }
    else
    {
        cout<<-1<<endl;
    }
}

int main()
{
    memset(dis,62,sizeof(dis));
    cin>>n>>m;
    unsigned int a,b,c,d,last=0;
    while(m>0)
    {
        m--;
        cin>>a>>b>>c;
        if(a==1)
        {
            cin>>d;
            dis[b][c]=min(d,dis[b][c]);
            dis[c][b]=min(d,dis[c][b]);
        }
        else if(last==0)
        {
            out(b,c);
        }
        else
        {
            floyd();
            out(b,c);
        }
        last=a;
    }
    return 0;
}

//Dij
#include <iostream>
#include <cstring>

using namespace std;

int dis[101][101];
int n,m;
int vis[101];

int main()
{
    memset(dis,62,sizeof(dis));
    cin>>n>>m;
    int a,b,c,d,tag,index;
    int i;
    while(m>0)
    {
        m--;
        cin>>a>>b>>c;
        if(a==1)
        {
            cin>>d;
            dis[b][c]=min(d,dis[b][c]);
            dis[c][b]=min(d,dis[c][b]);
        }
        else
        {
            for(i=1;i<=n;i++)
            {
                vis[i]=dis[b][i];
            }
            while(true)
            {
                tag=vis[b];
                index=b;
                for(i=1;i<=n;i++)
                {
                    if(vis[i]<tag&&vis[i]!=-1)
                    {
                        tag=vis[i];
                        index=i;
                    }
                }
                if(index==c)
                {
                    cout<<tag<<endl;
                    break;
                }
                else if(index==b)
                {
                    cout<<-1<<endl;
                    break;
                }
                for(i=1;i<=n;i++)
                {
                    if(vis[i]!=-1&&i!=b)
                    {
                        vis[i]=min(vis[i],tag+dis[index][i]);
                    }
                }
                vis[index]=-1;
            }
        }
    }
    return 0;
}

无脑c++ spfa模板
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int MAXN=5010;

const int INF=10000000;

struct edge{
int to,cost;
};

vector<edge>G[MAXN];

int d[MAXN],n,m;

bool exist[MAXN];

queue<int>q;

void spfa(int s){
fill(d+1,d+n+1,INF);
d[s]=0;
memset(exist,false,sizeof(exist));
q.push(s);
exist[s]=true;
while(!q.empty()){
int v=q.front();
q.pop();
exist[v]=false;
for (int i=0;i<G[v].size();i++){
edge e=G[v][i];
if (d[v]+e.cost<d[e.to]){
d[e.to]=d[v]+e.cost;
if (!exist[e.to]){
q.push(e.to);
exist[e.to]=true;
}
}
}
}
}
int main(){
cin>>n>>m;
for (int i=1;i<=m;i++){
int a,s,t,u,v,e;
cin>>a;
if (a==0){
cin>>s>>t;
spfa(s);
if (d[t]==INF) cout<<-1<<endl;
else cout<<d[t]<<endl;
}
else {
cin>>u>>v>>e;
G[u].push_back((edge){v,e});
G[v].push_back((edge){u,e});
}
}
return 0;
}
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int MAXN=5010;

const int INF=10000000;

struct edge{
int to,cost;
};

vector<edge>G[MAXN];

int d[MAXN],n,m;

bool exist[MAXN];

queue<int>q;

void spfa(int s){
fill(d+1,d+n+1,INF);
d[s]=0;
memset(exist,false,sizeof(exist));
q.push(s);
exist[s]=true;
while(!q.empty()){
int v=q.front();
q.pop();
exist[v]=false;
for (int i=0;i<G[v].size();i++){
edge e=G[v][i];
if (d[v]+e.cost<d[e.to]){
d[e.to]=d[v]+e.cost;
if (!exist[e.to]){
q.push(e.to);
exist[e.to]=true;
}
}
}
}
}
int main(){
cin>>n>>m;
for (int i=1;i<=m;i++){
int a,s,t,u,v,e;
cin>>a;
if (a==0){
cin>>s>>t;
spfa(s);
if (d[t]==INF) cout<<-1<<endl;
else cout<<d[t]<<endl;
}
else {
cin>>u>>v>>e;
G[u].push_back((edge){v,e});
G[v].push_back((edge){u,e});
}
}
return 0;
}

/*
好题~深入透彻地进一步了解了bellman-ford算法~
这道题最朴素的做法就是对于加入的边直接加入团
然后再直接Dijkstra然后计算单源最短路~
但是还是比较麻烦的
其实有更好更巧妙的做法
窝们来想一下bellman-ford的算法过程
窝们都是用一条边<u,v>来松弛距离~
所以这里也可以尝试套用这种思想
因为n很小也就100
直接开个邻接矩阵记录距离初始化INF
然后对于次查询s t直接对应查询d[s][t]即可
然后如果有加入边
那么我们用O(n^2)的时间
枚举所有的一对点的距离尝试能不能用这条边<u,v>来松弛他们的距离
d[i][j]=min(d[i][j],d[i][x]+w+d[y][j])
d[i][j]=min(d[i][j],d[i][y]+w+d[x][j])
注意这里的松弛是要两端的
因为两端都有可能被用来松弛~
这样程序就非常好写了
复杂度也是O(n^2*m)
主要是编程复杂度非常低~
很巧妙啦~~~速度也比直接裸的Dijkstra速度快了一倍~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=105;
const int MAXM=1005;
const int INF=(1<<28)-1;
int d[MAXN][MAXN];
int n,m,tot;

void init()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                d[i][j]=INF;
}

void relax(int x,int y,int w)
{
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][x]+w+d[y][j]),
                d[i][j]=min(d[i][j],d[i][y]+w+d[x][j]);
}

void work()
{
    int k,x,y,w;
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        if(k==0)
        {
            cin>>x>>y;
            if(d[x][y]==INF)
                cout<<-1<<endl;
            else
                cout<<d[x][y]<<endl;
        }
        else
        {
            cin>>x>>y>>w;
            relax(x,y,w);
        }
    }
}

int main()
{
    init();
    work();
    return 0;
}
     

插入边后用新边更新其他所有的距离
枚举一个点对(i, j)尝试用这条新边来更新它。
更新的方式是在
dis[i][u] + dis[v][j] + c
和
dis[i][v] + dis[u][j] + c
中选一个较小的更新(c 是新边的边权)
还要注意加入的新边要与原来取小

#include <cstdio>
#include <cstring>
#include <iostream>

#define INF 1000000007

using namespace std;

typedef long long ll;

const int Maxn = 101;

int n, m;
ll map[Maxn][Maxn];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) map[i][j] = INF;    
    }
    for(int i = 1; i <= n; ++i) map[i][i] = 0;
    for(int i = 1; i <= m; ++i) {
        int opt, u, v; ll c; scanf("%d", &opt);
        if(opt == 1) {
            scanf("%d%d%lld", &u, &v, &c);
            map[u][v] = map[v][u] = min(map[u][v], c);
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= n; ++j) {
                    map[i][j] = min(map[i][j], min(map[i][u] + map[v][j] + c, map[i][v] + map[u][j] + c));
                }
            }
        }
        else {
            scanf("%d%d", &u, &v);
            if(map[u][v] != INF) printf("%lld\n", map[u][v]);   
            else puts("-1");
        }
    }
    return 0;
}

这道题无脑SPFA即可
var
i,j,k,l,o,p,m,n,head,tail,now,qd,zd,gg,t,w:longint;
f,a:array[0..10000,0..10000] of longint;
d,c,sl:array[0..10000] of longint;
function spfa(qd,zd:longint):longint;
var
i:longint;
begin
fillchar(sl,sizeof(sl),0);
fillchar(d,sizeof(d),0);
fillchar(c,sizeof(c),0);
for i:=1 to m do
d[i]:=maxlongint;
d[qd]:=0;
c[qd]:=1;
sl[1]:=qd;
head:=1;
tail:=1;
while head<=tail do
begin
now:=sl[head];
for i:=1 to f[now,0] do
if d[f[now,i]]>d[now]+a[now,f[now,i]] then
begin
d[f[now,i]]:=d[now]+a[now,f[now,i]];
if c[f[now,i]]=0 then begin
inc(tail);
sl[tail]:=f[now,i];
c[f[now,i]]:=1;
end;
end;
c[now]:=0;
inc(head);
end;
spfa:=d[zd];
end;

begin
readln(m,k);
for i:=1 to k do
begin
read(gg);
if gg=0 then begin
read(t,w);
readln;
if spfa(t,w)=maxlongint then writeln(-1) else writeln(spfa(t,w));
end;
if gg=1 then begin
read(o,p,l);
readln;
if ((a[o,p]<>0) and (l<a[o,p])) or (a[o,p]=0) then begin
inc(f[o,0]);
inc(f[p,0]);
f[o,f[o,0]]:=p;
f[p,f[p,0]]:=o;
a[o,p]:=l;
a[p,o]:=l;
inc(n);end;
end;
if i=k then halt;
end;
end.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int inf=1000010;
const int maxn=110;

int G[maxn][maxn],n,m,s,to,e;
bool k;

void Add(int u,int v,int t)
{
if(t>=G[u][v]) return;
G[u][v]=G[v][u]=t;
for(int i=1,temp;i<=n;++i) for(int j=1;j<=n;++j)
{
temp=min(G[i][u]+G[v][j],G[i][v]+G[u][j]);
G[j][i]=G[i][j]=min(G[i][j],temp+G[u][v]);
}
}

void Print(int from,int to)
{
printf("%d\n",(G[from][to]==inf)?-1:G[from][to]);
}

void init()
{
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) G[i][j]=(i==j)?0:inf;
}

int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;++i)
{
cin>>k>>s>>to;
if(k) {cin>>e;Add(s,to,e);}
else Print(s,to);
}
return 0;
}

首先为了偷懒就打了个floyd，然后。。。60分QAQ
所以还是得用dij啦~
CODE：（floyd懒得删）
const maxd=maxlongint;
var st,en,q:longint;
k,m,n,i,j:longint;
a:array[1..100,1..100] of int64;
procedure dij;
var i,j:longint;
dist:array[0..120] of int64;
used:array[0..120] of boolean;
k,best:int64;
begin
for i:=1 to n do begin
dist[i]:=a[st,i];used[i]:=false;
end;
dist[st]:=0;
used[st]:=true;
for i:=1 to n-1 do begin
best:=maxd;
for j:=1 to n do begin
if not used[j] and (dist[j]<=best) then begin
k:=j;best:=dist[j];
end;
end;
used[k]:=true;
for j:=1 to n do
if not used[j] and (dist[k]+a[k,j]<dist[j]) then begin
dist[j]:=dist[k]+a[k,j];
end;
end;
if dist[en]=maxd then writeln(-1) else writeln(dist[en]);
end;

procedure floyd;
var x,i,j:longint;
begin
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then a[i,j]:=a[i,x]+a[x,j];
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do a[i,j]:=maxd;
for i:=1 to m do begin
read(q,st,en);
if q=1 then begin
read(k);
if k<a[st,en] then begin
a[st,en]:=k;
a[en,st]:=k;
end;
end;
if q=0 then
dij;
readln;
end;
end.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,m;
long long f[101][101],dis[101];
bool b[101];
bool check(long long t)
{
if(t==dis[0]){
return false;
}
return true;
}
void work(int t,int y)
{
int i;
memset(b,false,sizeof(b));
memset(dis,127/3,sizeof(dis));
dis[t]=0;
while(1){
int k=0;
for(i=1;i<=n;i++){
if(dis[i]<dis[k]&&!b[i]){
k=i;
}
}
if(k==0){
break;
}
b[k]=true;
for(i=1;i<=n;i++){
if(dis[i]>dis[k]+f[k][i]){
dis[i]=dis[k]+f[k][i];
}
}
}
if(check(dis[y])){
printf("%lld\n",dis[y]);
}
else{
printf("-1\n");
}
}
void init()
{
int i,number,x,y,z;
memset(f,127/3,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d",&number);
if(number==1){
scanf("%d%d%d",&x,&y,&z);
if(z<f[x][y]){
f[x][y]=f[y][x]=z;
}
}
else{
scanf("%d%d",&x,&y);
work(x,y);
}
}
}
int main()
{
init();
return 0;
}

2.小岛
构建无向图G，起初无向图G的边集为空。之后每次若插入一条新的边，则可以对任意一对点<u,v>进行松弛操作，从而维护出最短路径。总时间复杂度O(MN^2)。
对于其它最短路径的算法，将示情况而得到20~100不等的分数。但是其它可以拿到满分的算法如基于配对堆的Dijkstra等，都相对比较复杂而难以实现。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define Maxn 101
ll A[Maxn][Maxn], dis[Maxn];
bool b[Maxn];
int N, M;

bool check(ll t) {
if(t == dis[0]) return 0;
return 1;
}

void Dijkstra(int u, int v) {
memset(b, 0, sizeof(b));
memset(dis, 127/3, sizeof(dis));
dis[u] = 0;
while(1) {
int k = 0;
for(int i=1; i<=N; i++)
if(dis[i]<dis[k] && !b[i])
k = i;

if(!k) break;
b[k] = 1;
for(int i=1; i<=N; i++)
if(dis[i] > dis[k]+A[k][i])
dis[i] = dis[k]+A[k][i];
}
if(check(dis[v])) printf("%lld\n", dis[v]);
else printf("%d\n", -1);
}

void work() {
memset(A, 127/3, sizeof(A));
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++) {
int t;
scanf("%d", &t);
if(t == 0) {
int u, v;
scanf("%d%d", &u, &v);
Dijkstra(u, v);
}
else if(t == 1) {
int u, v, s;
scanf("%d%d%d", &u, &v, &s);
if(s < A[u][v])
A[u][v] = A[v][u] = s;
}
}
}

int main() {

work();

return 0;
}

参考ahdoc：每添一条边，枚举所有的顶点用这条边松弛即可，O(mn^2)
http://blog.leanote.com/post/okami/855aabd52876

//用六个WrongAnswer告诉你这题用Dijkstra的话一定要单独用dis数组记录
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
int X[150][150]={0},dis[150]={0};
bool visited[150]={0};
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(X,-1,sizeof(X));
for(int i=0;i<m;i++)
{
int r;
scanf("%d",&r);
if(r==1)
{
int v,u,z;
scanf("%d%d%d",&u,&v,&z);
if(X[u][v]==-1||X[u][v]>z)
{
X[u][v]=z;
X[v][u]=z;
}
}
else if(r==0)
{
int u,v;
scanf("%d%d",&u,&v);
if(u==v)
printf("0");
else
{
memset(visited,0,sizeof(visited));
memset(dis,-1,sizeof(dis));
dis[u]=0;
while(1)
{
int pre=0;

for(int j=1;j<=n;j++)
{//printf("\n%d %d %d %d\n",minn,j,X[u][j],visited[j]);
if((!visited[j])&&(pre==0||dis[j]<dis[pre])&&dis[j]!=-1)
{
pre=j;
}
}
if(pre==0)
break;
visited[pre]=1;
for(int k=1;k<=n;k++)
if(k!=pre&&k!=u)
if((dis[k]==-1||dis[k]>dis[pre]+X[pre][k])&&(X[pre][k]!=-1&&dis[pre]!=-1))
{
dis[k]=X[pre][k]+dis[pre];
// printf("%d %d %d %d %d\n",pre,k,X[k][u],X[pre][k],X[u][pre]);
}
}
printf("%d\n",dis[v]);
}
}

}

return 0;
}

暮然回首 这题 是暴力。^_^
```
type
re=record
v,len,next:longint;
end;

var
n,m,i,tot,s,t,z,k:longint;
last:array[0..100]of longint;
dis:array[0..100]of int64;
q:array[0..1000]of longint;
flag:array[0..100]of boolean;
e:array[0..10000]of re;

procedure add(u,v,z:longint);
begin
inc(tot);
e[tot].v:=v;
e[tot].len:=z;
e[tot].next:=last[u];
last[u]:=tot;
end;

procedure spfa(s:longint);
var
i,x,tox,head,tail:longint;
begin
for i:=1 to 100 do
begin
flag[i]:=false;
dis[i]:=maxlongint;
end;
q[1]:=s; dis[s]:=0; flag[s]:=true;
head:=1; tail:=1;
while head<=tail do
begin
x:=last[q[head]];
while x<>0 do
begin
tox:=e[x].v;
if dis[tox]>dis[q[head]]+e[x].len then
begin
dis[tox]:=dis[q[head]]+e[x].len;
if not flag[tox] then
begin
flag[tox]:=true;
inc(tail);
q[tail]:=tox;
end;
end;
x:=e[x].next;
end;
inc(head);
flag[q[head]]:=false;
end;
end;

begin
assign(input,''); reset(input);
assign(output,''); rewrite(output);
readln(n,m);
for i:=1 to m do
begin
read(k);
if k=0 then
begin
read(s,t);
Spfa(s);
if dis[t]=maxlongint then writeln(-1) else writeln(dis[t]);
end else
begin
read(s,t,z);
add(s,t,z);
add(t,s,z);
end;
end;
close(input); close(output);
end.
```

Pascal题解
pascal
var
i,k,m,n,s,t,u,v,e:longint;
a:array[0..101,0..101]of qword;
flag:array[0..101]of boolean;
dis:array[0..101]of qword;
procedure dijkstra(x,y:longint);
var
i,k:longint;
begin
fillchar(flag,sizeof(flag),false);
fillchar(dis,sizeof(dis),127 div 3);
dis[x]:=0;
while true do
begin
k:=0;
for i:=1 to n do
if (not flag[i])and(dis[i]<dis[k]) then k:=i;
if k=0 then break;
flag[k]:=true;
for i:=1 to n do
if dis[i]>dis[k]+a[k,i] then dis[i]:=dis[k]+a[k,i];
end;
if dis[y]=dis[0] then writeln(-1) else writeln(dis[y]);
end;
begin
fillchar(a,sizeof(a),127 div 3);
readln(n,m);
for i:=1 to m do
begin
read(k);
if k=1 then
begin
readln(u,v,e);
if e>a[u,v] then continue;
a[u,v]:=e;a[v,u]:=e;
end
else
begin
readln(s,t);
dijkstra(s,t);
end;
end;
end.