[kuangbin带你飞]专题四 最短路练习

时间：2023-02-13 18:26:50

题目已经写了许久了，贴一下代码，以便自己以后的查阅。

A - Til the Cows Come Home 题目地址 
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <map>
#define INF 0x7ffffff
#define MAXN 159
using namespace std;

int n,m,start,end;
int g[1009][1009],d[1009],final[1009],ss[1009];

void Dijkstra(int s,int n)
{
    int v,Min;
    memset(final,0,sizeof(final));
    for(int i=1;i<=n;i++)
        d[i]=g[s][i];
    d[s]=0;
    final[s]=1;
    for(int i=1;i<=n;i++)
    {
        Min=INF;
        for(int w=1;w<=n;w++)
        {
            if(!final[w]&&d[w]<Min)
            {
                Min=d[w];
                v=w;
            }
        }
        if(v==INF)
            break;
        final[v]=1;
        for(int w=1;w<=n;w++)
        {
            if(!final[w]&&d[v]+g[v][w]<d[w])
            {
                d[w]=d[v]+g[v][w];
            }
        }
    }
    printf("%d\n",d[n]);
}

void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=g[j][i]=INF;
}

int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int T;
    scanf("%d%d",&T,&n);init();
    while(T--)
    {
        int a,b,time;
        scanf("%d%d%d",&a,&b,&time);
        if(g[a][b]>time)
        {
            g[a][b]=g[b][a]=time;
        }
    }
    Dijkstra(1,n);
    return 0;
}

B -  Frogger 题目地址
错的次数比较多，这个应该不是自己写的，当时贴的代码，最后再做一遍吧。。
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Sca_ld(x) scanf("%I64d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))

const int maxn=1010;
const int INF=99999999;

bool vis[maxn];
int pre[maxn];
int x[maxn];
int y[maxn];
double Map[maxn][maxn],ans[maxn];

void Dijkstra(double cost[][maxn],double lowcost[],int n,int beg)
{
	int i,j,k,Min;
	For2(i,1,n)
	{
		lowcost[i]=INF;
		vis[i]=false;
		pre[i]=-1;
	}
	lowcost[beg]=0;//起点初始化
	For2(j,1,n)
	{
		k=-1;
		Min=INF;
		For2(i,1,n)
			if (!vis[i]&&lowcost[i]<Min)
			{
				Min=lowcost[i];
				k=i;
			}
		if (k==-1) break;
		vis[k]=true;
		For2(i,1,n)
			if (!vis[i]&&(max(lowcost[k],cost[k][i])<lowcost[i])&&cost[k][i])
			{
				lowcost[i]=max(lowcost[k],cost[k][i]);
				pre[i]=k;
			}
	}
}

int main()
{
	//input;
	int t,n,a,b,c,i,j,k,Case=0;
	while(cin>>n,n)
	{
		Fill(x,0);
		Fill(y,0);
		Fill(Map,0);
		For2(i,1,n) Sca_d(x[i]),Sca_d(y[i]);
		For2(i,1,n-1)
			For2(j,i+1,n)
				Map[i][j]=Map[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		Dijkstra(Map,ans,n,1);
		printf("Scenario #%d\n",++Case);
		printf("Frog Distance = %.3f\n\n",ans[2]);
	}
	return 0;
}

C -  Heavy Transportation  题目地址 
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define inf 1<<29
#define min(a,b) (a<b?a:b)

const int maxn=1001;
int n,m;
int map[maxn][maxn];

int Dijkstra()
{
    int i,j,k;
    int dist[maxn];
    bool pre[maxn];
    for(i=1;i<=n;i++)
    {
        pre[i]=false;
        dist[i]=map[1][i];
    }

    for(i=1;i<=n;i++)
    {
        int mm=-1;
        for(j=1;j<=n;j++)
        {
            if(!pre[j]&&dist[j]>mm)
            {
                mm=dist[j];
                k=j;
            }
        }

        pre[k]=true;

        for(j=1;j<=n;j++)
        {
            if(!pre[j]&&dist[j]<min(dist[k],map[k][j]))
                dist[j]=min(dist[k],map[k][j]);
        }
    }
    return dist[n];
}
int main()
{
    int T,i,j;
    scanf("%d",&T);
    int t=1;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
                map[i][j]=0;
        for(i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        printf("Scenario #%d:\n",t++);
        printf("%d\n\n",Dijkstra());
    }
    return 0;
}

D -  Silver Cow Party  题目地址 
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const int MAXN=1005;

#define INF 0x7ffffff

int cost[MAXN][MAXN],cost2[MAXN][MAXN];
int lowcost[MAXN];
int pre[MAXN];
bool vis[MAXN];
int n;

void Dijkstra(int cost[][MAXN],int lowcost[],int n,int beg)
{
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=1;j<=n;j++)
    {
        int k=-1;
        int Min=INF;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&lowcost[i]<Min)
            {
                Min=lowcost[i];
                k=i;
            }
        }
        if(k==-1)
            break;
        vis[k]=true;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
        }
    }
}

void init()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            cost[i][j]=INF;
            cost2[j][i]=INF;
        }
}

int dis1[MAXN],dis2[MAXN];

int main()
{
    int m,start;
    while(scanf("%d%d%d",&n,&m,&start)==3)
    {
        init();
        memset(dis1,0,sizeof(dis1));
        memset(dis2,0,sizeof(dis2));
        for(int i=0;i<m;i++)
        {
            int a,b,time;
            scanf("%d%d%d",&a,&b,&time);
            if(cost[a][b]>time)
            {
                cost[a][b]=time;
            }
            if(cost2[b][a]>time)
            {
                cost2[b][a]=time;
            }
        }
        Dijkstra(cost,dis1,n,start);
        Dijkstra(cost2,dis2,n,start);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,dis1[i]+dis2[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

H -  Cow Contest 题目地址 
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const int MAXN=105;
int cost[MAXN][MAXN];

void Floyd(int n)
{
    for(int k=0;k<=n;k++)
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                cost[i][j]=(cost[i][k]&cost[k][j])||cost[i][j];
}

void init(int n)
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            if(i==j)
                cost[i][j]=1;
            else
                cost[i][j]=0;
        }
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        init(n);
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            cost[a][b]=1;
        }

        Floyd(n);

        int sum=0;
        for(int i=1;i<=n;i++)
        {
            int cnt=0;
            for(int j=1;j<=n;j++)
            {
                if(cost[j][i])
                    cnt++;
                if(cost[i][j])
                    cnt++;

            }
            if(cnt==n+1)
                sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}


标签：

相关文章