洛谷P1339HeatWave题解

发表于 | 评论数： | 阅读次数：

P1339[USACO09OCT]HeatWave

题意概述

The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the heat too much.
FJ has studied the routes that can be used to move milk from Wisconsin to Texas. These routes have a total of T (1 <= T <= 2,500) towns conveniently numbered 1..T along the way (including the starting and ending towns). Each town (except the source and destination towns) is connected to at least two other towns by bidirectional roads that have some cost of traversal (owing to gasoline consumption, tolls, etc.). Consider this map of seven towns; town 5 is the
source of the milk and town 4 is its destination (bracketed integers represent costs to traverse the route):

1
2
3
4
5
6
7
8
9
          [1]----1---[3]-
         /               \
  [3]---6---[4]---3--[3]--4
 /               /       /|
5         --[3]--  --[2]- |
 \       /        /       |
  [5]---7---[2]--2---[3]---
        |       /
       [1]------

Traversing 5-6-3-4 requires spending 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 total expenses.
Given a map of all the C (1 <= C <= 6,200) connections (described as two endpoints R1i and R2i (1 <= R1i <= T; 1 <= R2i <= T) and costs (1 <= Ci <= 1,000), find the smallest total expense to traverse from the starting town Ts (1 <= Ts <= T) to the destination town Te (1 <= Te <= T).

INPUT & OUTPUT’s examples

Input’s eg #1

1
2
3
4
5
6
7
8
9
10
11
12
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

Output’s eg #1

1
7

样例说明

1
5->6->1->4 (3+1+3)

分析

比较简单的一道图论基础题对吧。

题意非常明显，就是在一个无向图中求两个定点之间的最短路。

那么，我们就可以使用SPFA算法来做。

这里，我们定义两个vector不定长动态数组,一个是Map[i][j]存储这张地图，另一个是value[i][j]表示从i到j的路径的长度。

初始化之后，我们就可以开始求解了。定义一个队列queue<int>Q来作为求解队列。

首先，开始求解之前，我们假设所有的点距离都为inf，这时所有的点也都没有被访问过。

然后我们将起点入队，然后开始查找。当查找队列不为空时，我们取出队头first，将它的标记解除。

然后枚举与它相连的所有点i，如果选择first->i为其中一条路径，使得起点到i的距离更短，那么更新dist数组。

如果Map[first][i],不在队列里（即被松弛），那么把他加入队列，打上标记。

如此循环下去，答案就是dist[T]。

代码

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
103
104
105
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype> 
#include<queue>
#include<vector>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* consts */
const int MAXN = 2e4+10;
const int INF = 1e9;
/* definitions */
vector<int>Map[MAXN],value[MAXN];
int n,m,start,end;
int dist[MAXN];
bool visited[MAXN];
queue<int>Q;
/* functions */
inline void init(){
    scanf("%d%d%d%d",&n,&m,&start,&end);
    int s,e,val;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&s,&e,&val);
        Map[s].push_back(e);
        Map[e].push_back(s);
        value[s].push_back(val);
        value[e].push_back(val);
    }
}
inline void SPFA(){
    init();
    for(int i=1;i<=n;i++){
        dist[i]=INF;visited[i]=0;
    }
    dist[start]=0;visited[start]=1;
    Q.push(start);
    int first,tmp;
    while(!Q.empty()){
        first=Q.front();
        Q.pop();
        visited[first]=0;
        for(unsigned int i=0;i<Map[first].size();i++){
            tmp=dist[first]+value[first][i];
            if(tmp<dist[Map[first][i]]){
                dist[Map[first][i]]=tmp;
                if(!visited[Map[first][i]]){
                    Q.push(Map[first][i]);
                    visited[Map[first][i]]=1;
                }
            }
        }
    }
    printf("%d\n",dist[end]);
    return;
}
int main(int argc,char *argv[]){
    SPFA();
    return 0;
}

THE END