poj 3268(关键: 求点到终点的最短路)

112 阅读 0 评论 74 点赞

我是靠谱客的博主糟糕书本，这篇文章主要介绍poj 3268(关键: 求点到终点的最短路)，现在分享给大家，希望可以做个参考。

题目链接:http://poj.org/problem?id=3268

题意: 给定一张有向图以及一个点x，求从每个点到点x的最短距离与点x到每个点的最短距离的和最大

关键: 如果知道在存图的时候将图反向存, 然后以点 x 为起点跑一边dij, 求得的redis[] 数组即原图每个点到x 的最短距离

AC代码:

复制代码

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
vector<pair<int,int> >E[maxn];
vector<pair<int,int> >REE[maxn];
int dis[maxn];
int redis[maxn];

void init(){
    for(int i = 0;i < maxn;i ++){
        E[i].clear();
        REE[i].clear();
        dis[i] = inf;
        redis[i] = inf;
    }
}

void dij(int s,int *d,vector<pair<int,int> > *e){
    d[s] = 0;
    priority_queue<pair<int,int> >Q;
    Q.push(make_pair(-d[s],s));
    while(!Q.empty()){
        int now = Q.top().second;
        Q.pop();
        for(int i = 0;i < e[now].size();i ++){
            int to = e[now][i].first;
            if(d[to] > d[now] + e[now][i].second){
                d[to] = d[now] + e[now][i].second;
                Q.push(make_pair(-d[to],to));
            }
        }
    }
}

int main()
{
    int t,n,x;
    while(~scanf("%d%d%d",&t,&n,&x)){
        int a,b,c;
        init();
        for(int i = 0;i < n;i ++){
            scanf("%d%d%d",&a,&b,&c);
            E[a].push_back(make_pair(b,c));
            REE[b].push_back(make_pair(a,c));
        }
        dij(x,redis,REE); dij(x,dis,E);
        int maxx = -1;
        for(int i = 1;i <= t;i ++){
            if(maxx < dis[i] + redis[i]) maxx = dis[i] + redis[i];
        }
        printf("%dn",maxx);
    }
    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
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
vector<pair<int,int> >E[maxn];
vector<pair<int,int> >REE[maxn];
int dis[maxn];
int redis[maxn];

void init(){
    for(int i = 0;i < maxn;i ++){
        E[i].clear();
        REE[i].clear();
        dis[i] = inf;
        redis[i] = inf;
    }
}

void dij(int s,int *d,vector<pair<int,int> > *e){
    d[s] = 0;
    priority_queue<pair<int,int> >Q;
    Q.push(make_pair(-d[s],s));
    while(!Q.empty()){
        int now = Q.top().second;
        Q.pop();
        for(int i = 0;i < e[now].size();i ++){
            int to = e[now][i].first;
            if(d[to] > d[now] + e[now][i].second){
                d[to] = d[now] + e[now][i].second;
                Q.push(make_pair(-d[to],to));
            }
        }
    }
}

int main()
{
    int t,n,x;
    while(~scanf("%d%d%d",&t,&n,&x)){
        int a,b,c;
        init();
        for(int i = 0;i < n;i ++){
            scanf("%d%d%d",&a,&b,&c);
            E[a].push_back(make_pair(b,c));
            REE[b].push_back(make_pair(a,c));
        }
        dij(x,redis,REE); dij(x,dis,E);
        int maxx = -1;
        for(int i = 1;i <= t;i ++){
            if(maxx < dis[i] + redis[i]) maxx = dis[i] + redis[i];
        }
        printf("%dn",maxx);
    }
    return 0;
}