Day4-A-最短路 HDU2544

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

Input输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间Sample Input

Sample Output

3

2

简单的最短路板子题，用来练习各种算法，代码如下：
dijkstra：

const int maxm = ;

const int INF = 0x7fffffff;

int N, M, G[maxm][maxm], d[maxm], vis[maxm];

struct Node {

    int sum, i;

    Node(int _sum, int _i) : sum(_sum), i(_i){}

    bool operator<(const Node &a) const {

        return a.sum < sum;

    }

};

void init() {

    for (int i = ; i <= N; ++i) {

        d[i] = INF;

    }

    memset(G, , sizeof(G)), memset(vis, , sizeof(vis));

}

int main() {

    while(scanf("%d%d",&N,&M) && N + M) {

        init();

        for (int i = ; i < M; ++i) {

            int t1, t2, t3;

            scanf("%d%d%d", &t1, &t2, &t3);

            G[t1][t2] = G[t2][t1] = t3;

        }

        priority_queue<Node>q;

        q.push(Node(, ));

        while(!q.empty()) {

            Node p = q.top();

            q.pop();

            if(vis[p.i]++)

                continue;

            for (int i = ; i <= N; ++i) {

                if(G[p.i][i] && G[p.i][i] + d[p.i] < d[i]) {

                    d[i] = G[p.i][i] + d[p.i];

                    q.push(Node(d[i],i));

                }

            }

        }

        printf("%d\n", d[N]);

    }

    return ;

}

　Bellman_Ford:

const int maxm = ;

const int maxn = ;

const int INF = 0x7fffffff;

int N, M, v[maxn], u[maxn], cost[maxn], d[maxm];

void init() {

    memset(v, , sizeof(v)), memset(u, , sizeof(u)), memset(cost, , sizeof(cost));

    for (int i = ; i <= N; ++i)

        d[i] = INF;

}

int main() {

    while(scanf("%d%d",&N,&M) && N + M) {

        init();

        for (int i = ; i < M; ++i) {

            int t1, t2, t3;

            scanf("%d%d%d", &t1, &t2, &t3);

            v[i * ] = t1, u[i * ] = t2, cost[i * ] = t3;

            v[i *  + ] = t2, u[i *  + ] = t1, cost[i *  + ] = t3;

        }

        for (int j = ; j < N-; ++j) {

            for (int i = ; i < M * ; ++i) {

                int x = v[i], y = u[i], c = cost[i];

                if(d[x] < INF)

                    d[y] = min(d[y], d[x] + c);

            }

        }

        printf("%d\n", d[N]);

    }

    return ;

}

SPFA:

const int maxm = ;

const int INF = 0x7fffffff;

int N, M, G[maxm][maxm], d[maxm], inq[maxm];

struct Node {

    int sum, i;

    Node(int _sum, int _i) : sum(_sum), i(_i){}

};

void init() {

    for (int i = ; i <= N; ++i) {

        d[i] = INF;

    }

    memset(G, , sizeof(G)), memset(inq, , sizeof(inq));

}

int main() {

    while(scanf("%d%d",&N,&M) && N + M) {

        init();

        for (int i = ; i < M; ++i) {

            int t1, t2, t3;

            scanf("%d%d%d", &t1, &t2, &t3);

            G[t1][t2] = G[t2][t1] = t3;

        }

        queue<int>q;

        q.push();

        inq[] = ;

        while(!q.empty()) {

            int u = q.front();

            q.pop();

            inq[u] = ;

            for (int i = ; i <= N; ++i) {

                if(G[u][i] && G[u][i] + d[u] < d[i]) {

                    d[i] = G[u][i] + d[u];

                    if(!inq[i])

                        q.push(i);

                }

            }

        }

        printf("%d\n", d[N]);

    }

    return ;

}

　Floyd:

const int maxm = ;

const int INF = 0x7fffffff;

int N, M, G[maxm][maxm];

void init() {

    for(int i = ; i <= N; ++i) {

        for (int j = ; j <= N; ++j) {

            if(i == j)

                G[i][i] = ;

            else

                G[i][j] = INF;

        }

    }

}

int main() {

    while(scanf("%d%d",&N,&M) && N + M) {

        init();

        for (int i = ; i < M; ++i) {

            int t1, t2, t3;

            scanf("%d%d%d", &t1, &t2, &t3);

            G[t1][t2] = G[t2][t1] = t3;

        }

        for (int k = ; k <= N; ++k)

            for(int i = ; i <= N; ++i)

                for (int j = ; j <= N; ++j) {

                    if(G[i][k] < INF && G[k][j] < INF)

                        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

                }

        printf("%d\n", G[][N]);

    }

    return ;

}

巴特西

Day4-A-最短路 HDU2544

最新文章

热门文章