注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1075.安全网络 ver.2  

2011-12-03 19:19:41|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1075.安全网络 ver.2
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 1492 (484 users)         Accepted: 782 (463 users)
[ My Solution ]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

21

Source
xmu
 
单源最短路,用了模版,呵呵。。。。
#include <cstdio>
#include <iostream>
#define inf 0x3fffffff
using namespace std;
#define MAXN 101
typedef int elem_t;
void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min)
{
 int v[MAXN],i,j,k, pre[MAXN];
 for (i=0;i<n;i++)
  min[i]=inf,v[i]=0,pre[i]=-1;
 for (min[s]=0,j=0;j<n;j++)
 {
  for (k=-1,i=0;i<n;i++)
   if (!v[i]&&(k==-1||min[i]<min[k]))
    k=i;
  for (v[k]=1,i=0;i<n;i++)
   if (!v[i]&&min[k]+mat[k][i]<min[i])
    min[i]=min[k]+mat[pre[i]=k][i];
 }
}
int main()
{
    int i, j, n;
 int a[101][101];
 int d[101];
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    dijkstra(n, a, 0, d);
    printf("%d\n", d[n-1]);
return 0;
}
 
 
  评论这张
 
阅读(275)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017