Article From:https://www.cnblogs.com/cangT-Tlan/p/9064022.html

Title Background

The cold area of northern Siberia is located in an island group of N islands. We numbered these islands in sequence from 1 to N.

Title Description

At first, there was no route between the islands. Later, with the development of transportation, some routes connecting two small islands gradually appeared. For example, add a route between u island and V Island, which takes e time. So along this route, people on the island of u can go ahead.On the island of V, people on the same island V can also go to u Island, and the time spent along this route is e.

At the same time, with the development of tourism, more and more people come to visit. So the shortest path between the two islands has become a topic of great concern.

Input-output format

Input format:

 

Enter a common M+1 line.

The first line has two integers N and M, which denote the number of islands and the total operands.

The next M line, each row represents an operation. The format is as follows:

0 s t:They asked for the shortest time to use the island from s Island to t Island (1< =s< =n, 1< =t< =n, s\neq T).

1 u v e:It added a new route from u island to V Island, with two-way e (1< =u< =n, 1< =v< =n, u v v, =n; U).

 


Output format:

 

Output for each query, output a single row.

For each group of queries, if there is no viable Road, output -1, otherwise the output will be used at the shortest time.

 

Input and output sample

Input sample #1: replication

3 8 
1 3 1 10 
0 2 3 
1 2 3 20 
1 1 2 5 
0 3 2 
1 1 3 7 
1 2 1 9 
0 2 3
Output sample #1: replication

-1
15
12
Input sample #2: replication

5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3
Output sample #2: replication

5955
21431
9298
16392
24774
8840

Explain

For 20% of the data, N< =5 and M< =30.

For 40% of the data, N< =20 and M< =200.

For 60% of the data, N< =80 and M< =500.

For 80% of the data, N< =100 and M< =2500.

For 100% of the data, N< =100 and M< =5000.

Idea: SPFA board.

#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 10002
using namespace std;
deque<int>que;
int n,m,s,t,tot,x;
int vis[MAXN],num[MAXN],dis[MAXN];
int to[MAXN],net[MAXN],cap[MAXN],from[MAXN];
void add(int u,int v,int w){
    to[++tot]=v;net[tot]=from[u];cap[tot]=w;from[u]=tot;
}
bool spfa(int s){
    for(int i=1; i<=n; i++)    dis[i]=2147483647;
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
    while(!que.empty())    que.pop_front();
    que.push_back(s);
    vis[s]=1;num[s]++;dis[s]=0;
    while(!que.empty()){
        int now=que.front();
        que.pop_front();vis[now]=0;
        for(int i=from[now]; i; i=net[i])
            if(dis[to[i]]>dis[now]+cap[i]){
                dis[to[i]]=dis[now]+cap[i];
                if(!vis[to[i]]){
                    if(!que.empty()&&dis[to[i]]>dis[que.front()])    que.push_back(to[i]);
                    else    que.push_front(to[i]);
                    if(++num[to[i]]>n)    return false;
                    vis[to[i]]=1;
                }
            }
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d",&x);
        if(x==1){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }            
        else{
            scanf("%d%d",&s,&t);
            int a=spfa(s);
            if(dis[t]==2147483647||!a)    printf("-1\n");
            else    printf("%d\n",dis[t]);
        }            
    }    
}

 

Link of this Article: P2683 small island

Leave a Reply

Your email address will not be published. Required fields are marked *