即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【最短路各类办法求解一题(模板题)】POJ 2387 Til the Cows Come Home

编程语言 bbbbswbq 15℃ 0评论

Problem Description

输入T,N分别代表有T条通道,和N个地点。接下来T行u,v,w分别表示u地点于v地点之间通道消费,有重复边

Sample Input

5 5


1 2 20


2 3 30


3 4 20


4 5 20


1 5 100

Sample Output

90

代码:dijkstra,就不带注解了,详细算法学习可以百度,只为留个模板复习用

#include
using namespace std;
const int INF = 0x3f3f3f3f;
int Map[1005][1005], n;
int vis[1005], dist[1005];
void dijkstra(int u)
{
    int i, Min, j, k;
    for(i = 1; i <= n; i++)
    {
        vis[i] = 0;
        dist[i] = Map[u][i];
    }
    vis[u] = 1;
    for(i = 1; i < n; i++)
    {
        Min = INF;
        for(j = 1; j <= n; j++)
        {
            if(Min > dist[j] && !vis[j])
            {
                Min = dist[j];
                u = j;
            }
        }
        vis[u] = 1;
        for(k = 1; k <= n; k++)
        {
            if(dist[k] > dist[u] + Map[u][k] && Map[u][k] != INF && !vis[k])
            {
                dist[k] = dist[u] + Map[u][k];
            }
        }
    }
    printf("%d\n", dist[1]);
}
int main()
{
    int T, i, j, u, v, w;
    while(~scanf("%d %d", &T, &n))
    {
        for(i = 0; i <= n; i++)
        {
            for(j = 0; j <= n; j++)
            {
                if(i == j) Map[i][j] = 0;
                else Map[i][j] = INF;
            }
        }
        while(T--)
        {
            scanf("%d %d %d", &u, &v, &w);
            if(Map[u][v] > w) Map[u][v] = Map[v][u] = w;
        }
        dijkstra(n);
    }
    return 0;
}

bellman_Ford

#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
struct node
{
    int u, v, w;
};
node Map[2005];
int n, m, dist[1005];
void bellman_Ford(int u)
{
    int i, j;
    for(i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
    dist[u] = 0;
    for(i = 1; i <= n - 1; i++)
    {
        for(j = 1; j <= m; j++)
        {
            if(dist[Map[j].v] > dist[Map[j].u] + Map[j].w)
                dist[Map[j].v] = dist[Map[j].u] + Map[j].w;
            if(dist[Map[j].u] > dist[Map[j].v] + Map[j].w)
                dist[Map[j].u] = dist[Map[j].v] + Map[j].w;
        }
    }
    printf("%d\n", dist[1]);
}
int main()
{
    int i;
    while(~scanf("%d %d", &m, &n))
    {
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &Map[i].u, &Map[i].v, &Map[i].w);
        }
        bellman_Ford(n);
    }
    return 0;
}

Spfa + 前向星

#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
struct node
{
    int to, w, next;
};
node Map[40005];
int n, head[1005];
int vis[1005], dist[1005];
void spfa(int u)
{
    int i, to, w;
    queue<int> q;
    for(i = 1; i <= n; i++)
    {
        vis[i] = 0;
        dist[i] = INF;
    }
    vis[u] = 1; dist[u] = 0;
    q.push(u);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        vis[u] = 0;
        for(i = head[u]; ~i; i = Map[i].next)
        {
            to = Map[i].to, w = Map[i].w;
            if(dist[to] > dist[u] + w)
            {
                dist[to] = dist[u] + w;
                if(!vis[to])
                {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    printf("%d\n", dist[1]);
}
int main()
{
    int T, u, v, w;
    while(~scanf("%d %d", &T, &n))
    {
        memset(head, -1, sizeof(head));
        int cnt = 0;
        while(T--)
        {
            scanf("%d %d %d", &u, &v, &w);
            Map[cnt].to = v;
            Map[cnt].w = w;
            Map[cnt].next = head[u];
            head[u] = cnt++;
            Map[cnt].to = u;
            Map[cnt].w = w;
            Map[cnt].next = head[v];
            head[v] = cnt++;
        }
        spfa(n);
    }
    return 0;
}

转载请注明:CodingBlog » 【最短路各类办法求解一题(模板题)】POJ 2387 Til the Cows Come Home

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情