洛谷_P1339 [USACO09OCT]Heat Wave G_最短路

[USACO09OCT]Heat Wave G

题目描述

有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $s$ 到 $t$ 的最短路长度。

输入格式

第一行四个正整数 $n,m,s,t$。
接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$，长为 $w$ 的边。

输出格式

输出一行一个整数，表示答案。

样例 #1

样例输入 #1

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
1
2
3
4
5
6
7
8
9
10
11
12

样例输出 #1

7
1

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n\le 2500$，$1\le m\le 6200$，$1\le w\le 1000$。

【样例说明】
$5\to 6\to 1\to 4$ 为最短路，长度为 $3+1+3=7$。

//
#include
using namespace std;

const int INF=0x3f3f3f3f;
const int N=2e6+7;
int h[N],pos;
struct edge{ int y,data,next; }e[N];
int n,m,s,t;

int dis[N];
bool used[N];

void init()
{
    pos=0;
    memset( h,-1,sizeof( h ) );
    memset( dis,0x3f,sizeof( dis ) );
    memset( used,0,sizeof( used ) );
}

void add( int x,int y,int data )
{
    e[pos].y=y;
    e[pos].data=data;
    e[pos].next=h[x];
    h[x]=pos++;
}

struct A
{
    int id,dis;
    A( int id,int dis ):id(id),dis(dis) {}
    
    bool operator < ( const A& in ) const
    {
        return in.dis < dis;
    }
};

void dijkstra()
{
    dis[s]=0;

    int x,y,data,i;
    priority_queue<A> q;
    q.push( A( s,0 ) );

    while( !q.empty() )
    {
        x=q.top().id; q.pop();
        if( used[x] ) continue;
        used[x]=1;

        for( i=h[x];~i;i=e[i].next )
        {
            y=e[i].y; data=e[i].data;
            if( dis[y]>dis[x]+data )
            {
                dis[y]=dis[x]+data;
                q.push( A( y,dis[y] ) );
            }
        }
    }
}

inline int read()
{
    int f=1;
    int data=0;
    char ch=getchar();

    while( !isdigit(ch) )
    {
        if( ch=='-' ) f=-1;
        ch=getchar();
    }
    while( isdigit(ch) )
    {
        data=( data<<3 )+( data<<1 )+( ch^48 );
        ch=getchar();
    }
    return data*f;
}

int main()
{
    int x,y,data,i;

    n=read(),m=read(),s=read(),t=read();
    init();
    while( m-- )
    {
        x=read(),y=read(),data=read();
        add( x,y,data );
        add( y,x,data );
    }
    dijkstra();
    printf("%d\n",dis[t]);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102