/ Vijos / 题库 / 小岛 /

题解

14 条题解

  • 1
    @ 2019-08-19 20:13:41

    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;
    }
    
  • 1
    @ 2018-04-13 23:05:28

    无脑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;
    }

  • 0
    @ 2018-08-20 09:25:19
    /*
    好题~深入透彻地进一步了解了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;
    }
         
    
  • 0
    @ 2017-10-30 21:28:35

    插入边后用新边更新其他所有的距离
    枚举一个点对(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;
    }
    
  • 0
    @ 2017-07-22 13:17:34

    这道题无脑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.

  • 0
    @ 2016-10-08 20:25:47

    #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;
    }

  • 0
    @ 2016-03-31 23:38:18

    首先为了偷懒就打了个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.

  • 0
    @ 2015-10-19 19:37:22

    #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;
    }

  • 0
    @ 2015-04-19 15:49:30

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

  • -1
    @ 2017-04-07 20:25:26

    #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;
    }

  • -1
    @ 2017-03-27 19:25:54

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

  • -1
    @ 2016-11-16 21:31:16

    //用六个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;
    }

  • -1
    @ 2016-11-10 19:37:33

    暮然回首 这题 是暴力。^_^
    ```
    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.
    ```

  • -2
    @ 2016-03-22 21:33:38

    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.

  • 1

信息

ID
1942
难度
6
分类
(无)
标签
递交数
690
已通过
188
通过率
27%
被复制
2
上传者