1077.安全網(wǎng)絡(luò) ver.4
Time Limit: 5000 MS         Memory Limit: 65536 K 
Total Submissions: 812 (143 users)         Accepted: 323 (120 users) 
[ My Solution ] 

Description
　　現(xiàn)在有個(gè)一個(gè)內(nèi)部局域網(wǎng)絡(luò)，里面有N臺(tái)機(jī)器。為了某種安全原因的考慮，有些機(jī)器之間是無法直接通訊的，即使可以通訊，機(jī)器與機(jī)器之間的通訊都是經(jīng)過加密的。由于不同機(jī)器之間傳輸?shù)膬?nèi)容不同，所以他們通訊采用的加密級(jí)別也不大相同。不同的加密級(jí)別導(dǎo)致破解的難度不一樣，越高的加密級(jí)別破解需要的時(shí)間也越多。如果我們獲得了編號(hào)為i的機(jī)器的完全控制權(quán)，且機(jī)器i和機(jī)器j可以直接通訊，另外我們破解了機(jī)器i和機(jī)器j之間的加密信息，那么我們就得到了機(jī)器j的完全控制權(quán)。
　　現(xiàn)在你通過了某種手段入侵了1號(hào)機(jī)器，得到了這臺(tái)機(jī)器的完全控制權(quán)，但是這個(gè)網(wǎng)絡(luò)里面最重要的東西不在這臺(tái)機(jī)器上，而在編號(hào)為N的機(jī)器上。由于需要破解加密信息才能控制其它機(jī)器，你又不想浪費(fèi)太多時(shí)間在破解上，現(xiàn)在你來算算你至少需要多少時(shí)間才能得到編號(hào)為N的機(jī)器的完全控制權(quán)。



Input
　　輸入的第一行是兩個(gè)正整數(shù)N(0 < N <= 100,000) M(0 < M <= 200,000)，表示機(jī)器的數(shù)目和允許通訊的機(jī)器對(duì)數(shù)。
　　輸入的第二行開始到第M+1行，每行3個(gè)整數(shù)，A B T( 1 <= A, B <= N, T <= 10,000, A ≠ B)，表示機(jī)器A和機(jī)器B之間可以互相通訊，且破解這個(gè)通訊的時(shí)間是T。輸入保證不存在重復(fù)的AB對(duì)。



Output
　　輸出完全控制機(jī)器N的最少時(shí)間。如果無法滿足要求則輸出-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;   
}