首页 > 代码库 > 人活着系列之芳姐和芳姐的猪(最短路_SPFA+前向星)

人活着系列之芳姐和芳姐的猪(最短路_SPFA+前向星)

2024-07-20 07:55:08   222人阅读

人活着系列之芳姐和芳姐的猪

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

百年来，人活着是为了什么这个问题一直萦绕在人的脑海里，也一直困扰着人的思想。人活着就是活着了，为活着本身而活着，而不是为活着之外的任何事物而活着的。正因为活着，所以活着。对，是有点莫明其妙，但也是一句最受用的话。

m个猪圈，顺便在u，终点.....芳姐和猪们约定好，每天去一个固定猪圈去吃饭，芳姐为了不累着她可爱的猪们，想知道所有的猪吃饭走的最短路程是多少？

输入

 第一行n(1<=n<=350)，猪圈个数k(1<=k<=1200).（猪的编号为N+1行.

n+k+1行：v，两猪圈间距离（注：有的猪圈可能是空的，也可能有多头猪，保证<font face=‘\"Times‘ new="" roman,="" serif\"="">m个猪圈连通。

输出

 

示例输入

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

示例输出

8

提示

 

来源

 cz

示例程序


思路：最短路算法，为了复习一下SPFA+前向星，特意用这个写的，这个题也可以用floyd做。


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define inf 999999999
struct node
{
    int v,w;
    int next;
} edge[10010];
int head[1010];
int dis[1010][1010];//这里不同于其他的spfa，要用二维数组；
int vis[1010];
int same[1010];//因为有的是一个猪圈住好几个猪或者一个都不住，用same存储猪圈猪的个数；
int cnt,n,m;
void add(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void spfa(int s)
{
    int i;
    queue<int>q;
    for(i=1; i<=m; i++)
    {
        dis[s][i]=inf;
    }
    memset(vis,0,sizeof(vis));
    q.push(s);
    dis[s][s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[s][v]>dis[s][u]+edge[i].w)
            {
                dis[s][v]=dis[s][u]+edge[i].w;
                if(!vis[v])
                {
                  q.push(v);
                  vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    int k,i,j,t;
    int u,v,w;
    int sum;
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(same,0,sizeof(same));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&t);
            same[t]++;
        }
        for(i=1;i<=k;i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        for(i=1;i<=m;i++)//求每个顶点的最短路
        {
            spfa(i);
        }
        int minx=inf;
        for(i=1;i<=m;i++)
        {
            sum=0;
            for(j=1;j<=m;j++)
            {
                if(same[j]!=0)
                    sum+=dis[i][j]*same[j];
            }
            if(minx>sum)
            minx=sum;
        }
        printf("%d\n",minx);
    }
    return 0;
}





人活着系列之芳姐和芳姐的猪(最短路_SPFA+前向星)


联系
我们