E-Dijkstal

1005 输出用%f,1009别做了

Problem E

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 96   Accepted Submission(s) : 51

Problem Description

XiaoY is living in a big city, there are N towns in it and some towns near the sea. All these towns are numbered from 0 to N-1 and XiaoY lives in the town numbered ’0’. There are some directed roads connecting them. It is guaranteed that you can reach any town from the town numbered ’0’, but not all towns connect to each other by roads directly, and there is no ring in this city. One day, XiaoY want to go to the seaside, he asks you to help him find out the shortest way.

Input

There are several test cases. In each cases the first line contains an integer N (0<=N<=10), indicating the number of the towns. Then followed N blocks of data, in block-i there are two integers, Mi (0<=Mi<=N-1) and Pi, then Mi lines followed. Mi means there are Mi roads beginning with the i-th town. Pi indicates whether the i-th town is near to the sea, Pi=0 means No, Pi=1 means Yes. In next Mi lines, each line contains two integers S[sub]Mi[/sub] and L[sub]Mi[/sub], which means that the distance between the i-th town and the S[sub]Mi[/sub] town is L[sub]Mi[/sub].

Output

Each case takes one line, print the shortest length that XiaoY reach seaside.

Sample Input

5 1 0 1 1 2 0 2 3 3 1 1 1 4 100 0 1 0 1

Sample Output

2

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int map[][],dis[];
bool used[];
int sea[];
int n,k,minx;
void init()
{
    for(int i=;i<n;i++)
    {
        for(int j=;j<n;j++)
            {
                if(i==j) map[i][j] = ;
                     map[i][j] = INF;
            }
    }
}
void dijkstral(int s)
{
    memset(used,false,sizeof(used));
    for(int i=;i<n;i++)
    {
        dis[i] = map[][i];
    }

    dis[s] = ;
    while()
    {
        int v = -;
        for(int u=;u<n;u++)
        {
            if(!used[u]&&(v==-||dis[u]<dis[v]))    v = u;
        }
        if(v==-)    break;
        used[v] = true;
        for(int u=;u<n;u++)
        {
            dis[u] = min(dis[u],dis[v]+map[v][u]);
        }
    }
    int minm = INF;

    for (int i=;i<k;i++)
    {
        minm = min(minm,dis[sea[i]]);
    }
    printf ("%d\n",minm);
}
int main()
{
    int s,l;
    int M,P;
    int N;
    while(~scanf("%d",&N))
    {
    int cnt = ;
    int y = ;
    n = N;
    init();
    while(N--)
    {

        scanf("%d%d",&M,&P);
        if(P)
        {
            sea[y++] = cnt;
        }
        for(int i=;i<M;i++)
        {
            scanf("%d%d",&s,&l);
            map[cnt][s] = min(l,map[cnt][s]);
            map[s][cnt] = min(l,map[cnt][s]);
        }
        cnt++;
    }
    dijkstral();
}
    return ;
}

随机推荐

1. Jmeter之csv、用户自定义变量以及Query Type分析（八）

   很多童鞋不知道对于Jmeter的Query Type 不知道选哪个,为什么选,怎么选! 下面这边做个简单的分析, 那么首先什么是CSV Data Set Config,有什么用呢? CSV Data ...

2. try catch finally的一些用法

   一:例题: package test; import javax.swing.*; class AboutException { public static void main(String[] a) ...

3. DSP using MATLAB 示例Example2.4

   n = [0:10]; x = stepseq(0,0,10) - stepseq(10,0,10); [xe,xo,m] = evenodd(x,n); set(gcf,'Color',[1,1,1 ...

4. WPF中文字体问题

5. Python学习笔记04

   语句之后有冒号,表示有一个语句块,且以四个空格的缩进来表示隶属关系. 与C# 相比,没有了{},没有了(),被冒号和缩进取代了 if,while,for,range,continue,break if ...

6. nginx实现ssl反向代理实战

   登录认证account.free4lab.com需要提供ssl登录接口,ssl的原理看这篇博文,因为前面有反向代理nginx,所以这个需求就放在nginx实现了,否则可以放在web容器(jetty,t ...

7. kafka storm hbase性能

   kafka  单台机器部署 1个partition storm 单台机器部署 hbase 四台机器集群 机器配置大概是4G cpu 4G内存 从kafka 读出到storm,然后flush到hbase ...

8. POJ1769 Minimizing maximizer（DP + 线段树）

   题目大概就是要,给一个由若干区间[Si,Ti]组成的序列,求最小长度的子序列,使这个子序列覆盖1到n这n个点. dp[i]表示从第0个到第i个区间且使用第i个区间,覆盖1到Ti所需的最少长度 对于Si ...

9. 【Linux程序设计】之进程控制&守护进程

   这个系列的博客贴的都是我大二的时候学习Linux系统高级编程时的一些实验程序,都挺简单的. 实验题目:Linux环境下的进程控制 实验目的:熟悉并掌握Linux环境下进程的相关函数的应用:守护进程的概 ...

10. BZOJ3559 : [Ctsc2014]图的分割

    考试的时候看少了一行,导致暴力都写错额… 贾教说他出的这题水,但是我觉得并不水,那个结论还是很神的. 首先M(i)就是i的最小生成树的最大边, 设f[i]表示i属于哪个集合 我们把边按权值从小到大排序 ...