题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2544

题目描述

在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

思路

最短路裸题,这里给出Bellman-FordDijkstraFloyd算法。注意是无向图。

AC代码(Bellman-Ford $O(V E)$)

/*************************************************************************
    > File Name: 2544.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-10 Mon 15:31:55 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;

struct Edge{
    int from, to, cost;
} edge[10005*2];
int d[10005];
int N, M;  // 路口N, 路的数量M

bool bellman_ford(int s) {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    for(int i=1; i<=N-1; ++i)
        for(int j=1; j<=2*M; ++j) {
            Edge e=edge[j];
            // printf("%d %d %d\n", e.to, e.from, e.cost);
            if(d[e.to] > d[e.from] + e.cost)
                d[e.to] = d[e.from] + e.cost;
        }

    int flag = true; // 判断有没有负圈
    for(int j=1; j<=2*M; ++j)
        if(d[edge[j].to] > d[edge[j].from] + edge[j].cost) {
            flag = false;
            break;
        }
    return flag;
}

void solve() {
    cin.sync_with_stdio(false);
    while(cin >> N >> M)  {
        if(N==M && M==0)
            break;
        for(int i=1; i<=M; ++i) {
            cin >> edge[i].from >> edge[i].to >> edge[i].cost;
            edge[i+M].to = edge[i].from;
            edge[i+M].from = edge[i].to;
            edge[i+M].cost = edge[i].cost;
        }

        bellman_ford(1);
        // for(int i=1; i<=N; ++i)
            // cout << d[i] << endl;
        cout << d[N] << endl;

    }

}

int main()
{
#ifdef Oj
    freopen("2544.in", "r", stdin);
#endif
    solve();
    return 0;
}

AC代码(Dijkstra $O(|V|^2)$)

/*************************************************************************
    > File Name: 2544_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-11 Tue 14:14:59 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int MAXV = 105;
const int MAXE = 10005;
int cost[MAXV][MAXV];
int d[MAXV];
bool used[MAXV];
int V, E;

void dijkstra(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(used, 0, sizeof(used));
    d[s] = 0;

    while(true) {
        int v = -1;
        for(int u=1; u<=V; ++u) // 从未使用过的节点中选择一个距离最小的顶点,编号从1开始
            if(!used[u] && (v==-1 || d[u] < d[v])) v = u;
        if(v == -1) break;
        used[v] = true;
        for(int u=1; u<=V; ++u) // 顶点编号从1开始计算
            d[u] = min(d[u], d[v]+cost[v][u]);
    }
}


void solve() {
    cin.sync_with_stdio(false);
    while(cin >> V >> E) {
        if(V==E && V==0)
            break;
        int from, to, cst;
        memset(cost, 0x3f, sizeof(cost));
        for(int i=0; i<E; ++i) {
            cin >> from >> to >> cst;
            cost[from][to] = cost[to][from] = cst;
        }
        dijkstra(1);
        cout << d[V] << endl;
        // for(int i=1; i<=V; ++i)
            // cout << d[i] <<endl;
        // cout << endl;
    }
}

int main()
{
#ifdef Oj
    freopen("2544.in", "r", stdin);
#endif
    solve();
    return 0;
}

AC代码(Dijkstra $O(|E| log|V|)$)

/*************************************************************************
    > File Name: 2544_3.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-11 Tue 14:47:22 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

const int MAX_V = 105;
const int MAX_E = 10005;
struct edge {
    int to, cost;
    edge(int t, int c): to(t), cost(c){}
};
vector<edge> G[MAX_V];
int d[MAX_V];
typedef pair<int, int> P; // first是最短距离, second是顶点编号
int V, E;

void dijkstra(int s) {
    // greater<P>指定堆按照first从小到大的顺序取值
    priority_queue<P, vector<P>, greater<P> > que;
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    que.push(P(0, s));
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}



void solve() {
    cin.sync_with_stdio(false);
    while(cin >> V >> E) {
        if(V == E && E == 0)
            break;
        for(int i=0; i<E; ++i) {
            int from, to, cost;
            cin >> from >> to >> cost;
            G[from].push_back(edge(to, cost));
            G[to].push_back(edge(from, cost));
        }
        dijkstra(1);
        cout << d[V] << endl;
        for(int i=1; i<=V; ++i)
            G[i].clear();
    }
}

int main()
{
#ifdef Oj
    freopen("2544.in", "r", stdin);
#endif
    solve();
    return 0;
}

AC代码(Floyd $O(|V|^3)$)

/*************************************************************************
    > File Name: 2544_4.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-14 Fri 14:50:58 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int V, E; // 顶点数V, 边数E
int d[102][102];

void floyd() {
    for(int k=1; k<=V; ++k)
        for(int i=1; i<=V; ++i)
            for(int j=1; j<=V; ++j)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
    return;
}

void solve() {
    while(cin >> V >> E) {
        if(V == 0 && E==0)
            break;
        memset(d, 0x3f, sizeof(d));
        int  A, B, C;
        for(int i=0; i<E; ++i) {
            cin >> A >> B >> C;
            if(d[A][B] == INF) d[A][B] = d[B][A] = C;
            else d[A][B] = d[B][A] = min(d[A][B], C);
        }
        for(int i=1; i<=V;++i)
            d[i][i] = 0;
        floyd();
        cout << d[1][V] << endl;
    }

}

int main()
{
#ifdef Oj
    freopen("2544.in", "r", stdin);
#endif
    solve();
    return 0;
}