xmu 1075: 安全网络 ver.2(最短路模型)

时间:2020-12-13 11:42:42

1075: 安全网络 ver.2

题目描述

  现在有个一个内部局域网络,里面有N台机器。为了某种安全原因的考虑,每两台机器之间的通讯都是经过加密的。由于不同机器之间传输的内容不同,所以他们通讯采用的加密级别也不大相同。不同的加密级别导致破解的难度不一样,越高的加密级别破解需要的时间也越多。如果我们获得了编号为i的机器的完全控制权,另外我们破解了机器i和机器j之间的加密信息,那么我们就得到了机器j的完全控制权。
  现在你通过了某种手段入侵了1号机器,得到了这台机器的完全控制权。但是这个网络里面最重要的东西不在这台机器上,而在编号为N的机器上。由于需要破解加密信息才能控制其它机器,你又不想浪费太多时间在破解上,现在你来算算你至少需要多少时间才能得到编号为N的机器的完全控制权。

输入

  输入的第一行是一个正整数N(0 < N <= 100),表示机器的数目。
  输入的第二行开始到第N+1行,每行N个整数,第i+1行的第j个数字Tij表示破解机器i和机器j之间的加密算法所需要的时间,范围在[0..100,000]之间。另外Tij= Tji,Tii = 0。

输出

  输出完全控制机器N的最少时间。

样例输入

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

样例输出

21

提示

来源

xmu


思路:没啥好讲的,直接上最短路代码就行了。

代码:

#include<bits/stdc++.h>
#define maxn 110
#define INF 0x7fffffff

using namespace std;

int Map[maxn][maxn],vis[maxn],dis[maxn];
int N;

void SPFA(){//最短路算法
queue<int> Q;
memset(vis,0,sizeof(vis));
for(int i=2;i<=N;i++) dis[i]=INF;
Q.push(1);vis[1]=1;dis[1]=0;
while(!Q.empty()){
int tp=Q.front();Q.pop();vis[tp]=0;
for(int i=1;i<=N;i++){
if(Map[tp][i]+dis[tp]>=dis[i]) continue;
dis[i]=dis[tp]+Map[tp][i];
if(!vis[i]) Q.push(i),vis[i]=1;
}
}
printf("%d\n",dis[N]);
}


int main(){
//freopen("in.txt","r",stdin);
while(cin>>N){
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
scanf("%d",Map[i]+j);
SPFA();
}
return 0;
}