HDU - 2544 最短路

题意：最短路

思路：四个方法，复习 一下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

int nodenum,edgenum;
int map[MAXN][MAXN],dis[MAXN];
int vis[MAXN];

int Dijkstra(int s,int d){
    int temp,k;
    memset(vis,0,sizeof(vis));
    for (int i = 1; i <= nodenum; i++)
        dis[i] = (i == s ? 0 : map[s][i]);
    vis[s] = 1;
    dis[s] = 0;
    for (int i = 1; i <= nodenum; i++){
        temp = INF;
        for (int j = 1; j <= nodenum; j++)
            if (!vis[j] && temp > dis[j])
                temp = dis[k=j];
        if (temp == INF)
            break;
        vis[k] = 1;
        for (int j = 1; j <= nodenum; j++)
            if (!vis[j] && dis[j] > dis[k] + map[k][j])
                dis[j] = dis[k] + map[k][j];
    }
    return dis[d];
}

int main(){
    int start,end,cost;
    int ans;
    while (scanf("%d%d",&nodenum,&edgenum) != EOF && (nodenum+edgenum)){
        for (int i = 1; i <= nodenum; i++)
            for (int j = 1; j <= nodenum; j++)
                map[i][j] = INF;
        for (int i = 1; i <= edgenum; i++){
            scanf("%d%d%d",&start,&end,&cost);
            if (cost < map[start][end])
                map[start][end] = map[end][start] = cost;
        }
        ans = Dijkstra(1,nodenum);
        printf("%d\n",ans);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

int nodenum,edgenum;
int map[MAXN][MAXN],dis[MAXN];
int vis[MAXN];

struct edge{
    int u,v;
    int cost;
}e[MAXN*MAXN/2];

int Bellman_ford(int s,int d){
    for (int i = 1; i <= nodenum; i++)
        dis[i] = INF;
    dis[s] = 0;
    for (int i = 0; i < nodenum-1; i++)
        for (int j = 0; j < edgenum*2; j++)
            if (dis[e[j].v] > dis[e[j].u] + e[j].cost)
                dis[e[j].v] = dis[e[j].u] + e[j].cost;
    return dis[d];
}

int main(){
    int start,end,cost;
    int ans;
    while (scanf("%d%d",&nodenum,&edgenum) != EOF && nodenum+edgenum){
        for (int i = 0; i < edgenum; i++){
            scanf("%d%d%d",&start,&end,&cost);
            e[i*2].u = start,e[i*2].v = end,e[i*2].cost = cost;
            e[i*2+1].u = end,e[i*2+1].v = start,e[i*2+1].cost = cost;
        }
        ans = Bellman_ford(1,nodenum);
        printf("%d\n",ans);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

int nodenum,edgenum;
int map[MAXN][MAXN],dis[MAXN];
int vis[MAXN];

int Floyd(int s,int d){
    for (int k = 1; k <= nodenum; k++)
        for (int i = 1; i <= nodenum; i++)
            for (int j = 1; j <= nodenum; j++)
                map[i][j] = min(map[i][j],map[i][k]+map[k][j]);
    return map[s][d];
}

int main(){
    int s,e,cost;
    int ans;
    while (scanf("%d%d",&nodenum,&edgenum) != EOF && nodenum+edgenum){
        for (int i = 1; i <= nodenum; i++)
            for (int j = 1; j <= nodenum; j++)
                map[i][j] = INF;
        for (int i = 0; i < edgenum; i++){
            scanf("%d%d%d",&s,&e,&cost);
            if (cost < map[s][e])
                map[s][e] = map[e][s] = cost;
        }
        ans = Floyd(1,nodenum);
        printf("%d\n",ans);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

int nodenum,edgenum;
int map[MAXN][MAXN],dis[MAXN];
int vis[MAXN];

int spfa(int s,int d){
    queue<int> q;
    memset(vis,0,sizeof(vis));
    for (int i = 1; i <= nodenum; i++)
        dis[i] = INF;
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()){
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (int i = 1; i <= nodenum; i++){
            if (dis[i] > dis[cur] + map[cur][i]){
                dis[i] = dis[cur] + map[cur][i];
                if (!vis[i]){
                    q.push(i);
                    vis[i] = 1;
                }
            }
        }
    }
    return dis[d];
}

int main(){
    int s,e,c;
    int ans;
    while (scanf("%d%d",&nodenum,&edgenum) != EOF && nodenum+edgenum){
        for (int i = 1; i <= nodenum; i++)
            for (int j = 1; j <= nodenum; j++)
                map[i][j] = INF;
        for (int i = 0; i < edgenum; i++){
            scanf("%d%d%d",&s,&e,&c);
            if (c < map[s][e])
                map[e][s] = map[s][e] =  c;
        }
        ans = spfa(1,nodenum);
        printf("%d\n",ans);
    }
    return 0;
}

HDU - 2544 最短路,布布扣,bubuko.com

HDU - 2544 最短路

原文：http://blog.csdn.net/u011345136/article/details/20652941