1077.txt

厦门大学OJ上的ACM题1077源码

1077.安全网络 ver.4
Time Limit: 5000 MS         Memory Limit: 65536 K 
Total Submissions: 812 (143 users)         Accepted: 323 (120 users) 
[ My Solution ] 

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



Input
　　输入的第一行是两个正整数N(0 < N <= 100,000) M(0 < M <= 200,000)，表示机器的数目和允许通讯的机器对数。
　　输入的第二行开始到第M+1行，每行3个整数，A B T( 1 <= A, B <= N, T <= 10,000, A ≠ B)，表示机器A和机器B之间可以互相通讯，且破解这个通讯的时间是T。输入保证不存在重复的AB对。



Output
　　输出完全控制机器N的最少时间。如果无法满足要求则输出-1。



Sample Input
4 4
1 2 4
1 3 9
2 3 2
4 3 1



Sample Output
7




RunId 29524 of Problem 1077
Submit Time: 2008-11-01 21:45:37    Language: G++    Code Length: 1848 B 
    Result: Accepted    Time: 3532 MS    Memory: 7324 K    Judge: Apple 




#include <stdio.h>   
#include <stdlib.h>   
#define MAX 2000000000   
typedef struct arcnode{   
    long adjvex;   
    struct arcnode *nextarc;   
    long info;   
}arcnode;   
typedef struct{   
    arcnode *vertices[100001];   
    long vexnum, arcnum;   
}algraph;   
int main()   
{   
    algraph graph;   
    scanf("%ld %ld", &graph.vexnum, &graph.arcnum);   
    for (long s=1; s<=graph.vexnum; s++)   
        graph.vertices[s] = NULL;   
    for (long t=1; t<=graph.arcnum; t++){   
        arcnode *p = (arcnode*)malloc(sizeof(arcnode));   
        long vex;   
        scanf("%ld %ld %ld", &vex, &p->adjvex, &p->info);   
        p->nextarc = graph.vertices[vex];   
        graph.vertices[vex] = p;   
        arcnode *r = (arcnode*)malloc(sizeof(arcnode));   
        r->adjvex = vex;   
        r->info = p->info;   
        r->nextarc = graph.vertices[p->adjvex];   
        graph.vertices[p->adjvex] = r;   
    }   
    long *d = (long*)malloc((graph.vexnum+1)*sizeof(long));   
    for (long x=1; x<=graph.vexnum; x++)   
        d[x] = MAX;   
    bool *final = (bool*)calloc((graph.vexnum+1), sizeof(bool));   
    long *cur = (long*)malloc((graph.vexnum+1)*sizeof(long));   
    long mark = 1;   
    for (arcnode *p=graph.vertices[1]; p!=NULL; p=p->nextarc){   
        d[p->adjvex] = p->info;   
        cur[mark++] = p->adjvex;   
    }   
    final[1] = 1;   
    for (long i=1; i<=graph.vexnum; i++){   
        long max = MAX;   
        long v = 0;   
        long done;   
        for (long j=1; j<mark; j++)   
            if (d[cur[j]]<max){   
                v = cur[j];   
                max = d[v];   
                done = j;   
            }   
        if (max==2000000000 || v==graph.vexnum)   
            break;   
        cur[done] = cur[--mark];   
        final[v] = 1;   
        for (arcnode *q=graph.vertices[v]; q!=NULL; q=q->nextarc){   
            if (final[q->adjvex] == 1)   
                continue;   
            long temp = max + q->info;   
            if (temp < d[q->adjvex]){   
                if (d[q->adjvex] == MAX)   
                    cur[mark++] = q->adjvex;   
                d[q->adjvex] = temp;   
            }   
        }   
    }   
    if (d[graph.vexnum] == MAX)   
        printf("-1");   
    else  
        printf("%ld", d[graph.vexnum]);   
    return 0;   
}