描述

西伯利亞北部的寒地，坐落著由 N 個(gè)小島組成的島嶼群，我們把這些小島依次編號為 1 到 N 。

起初，島嶼之間沒有任何的航線。后來隨著交通的發(fā)展，逐漸出現(xiàn)了一些連通兩座小島的航線。
例如增加一條在 u 號小島與 v 號小島之間的航線，這條航線的用時(shí)為 e。 那么沿著這條航線，u 號小島上的人可以前往 v 號小島，同樣的 v 號小島上的人也可以前往 u 號小島，其中沿著這一條航線花費(fèi)的時(shí)間為 e。

同時(shí)，隨著旅游業(yè)的發(fā)展，越來越多的人前來游玩。那么兩個(gè)小島之間的最短路徑是多少便成為了飽受關(guān)注的話題。

格式

輸入格式

輸入共 M+1 行。

第一行有兩個(gè)整數(shù) N 和 M，分別表示小島的數(shù)與總操作數(shù)。

接下來的 M 行，每行表示一個(gè)操作，格式如下：
0 s t：表示詢問從 s 號小島到 t 號小島的最短用時(shí)（1<=s<=n, 1<=t<=n, s\neq t）。
1 u v e：表示新增了一條從 u 號小島到 v 號小島，用時(shí)為 e 的雙向航線（1<=u<=n, 1<=v<=n, u ≠ v, 1<=e<=10^6）。

輸出格式

輸出針對每一次詢問，單獨(dú)輸出一行。
對于每一組詢問來說，如果不存在可行的道路，則輸出 -1，否則輸出最短用時(shí)。

裸上SPFA #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;struct na{int y,z,ne;na(){ne=0;} }; int n,m,dis[101][101],c,x,y,z,p,l[101],r[101],num=0,k; na b[10001]; char o; queue <int> q; bool bo[101]; const int INF=1e9; inline int read(){p=0;o=getchar();while(o<'0'||o>'9') o=getchar();while(o>='0'&&o<='9') p=p*10+o-48,o=getchar();return p; } inline void in(int x,int y,int z){num++;if (l[x]==0) l[x]=num;else b[r[x]].ne=num;b[num].y=y;b[num].z=z;r[x]=num; } int main(){n=read();m=read();int i,j;for (i=1;i<=n;i++)for (j=1;j<=n;j++) dis[i][j]=INF;for (i=1;i<=n;i++) dis[i][i]=0;while(m--){c=read();x=read();y=read();if (c==0){if (dis[x][y]==INF) printf("-1\n");else printf("%d\n",dis[x][y]);}else{z=read();in(x,y,z);in(y,x,z);for (i=1;i<=n;i++){q.push(x);q.push(y);bo[x]=bo[y]=1;while(!q.empty()){k=q.front();q.pop();bo[k]=0;for (j=l[k];j;j=b[j].ne)if (dis[i][b[j].y]>dis[i][k]+b[j].z){dis[i][b[j].y]=dis[i][k]+b[j].z;if (!bo[b[j].y])q.push(b[j].y),bo[b[j].y]=1;}}}}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Enceladus/p/5121088.html

總結(jié)

以上是生活随笔為你收集整理的vijos 1942 [AH 2005] 小岛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。