【MOOC-浙大数据结构】第七周的编程作业——最短路+广搜输出路径

红太狼 2021-11-09 04:20 250阅读 0赞

1.**[哈利·波特的考试][Link 1]**

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<vector>
    using namespace std;
    const int inf=0x3f3f3f3f;
    int main()
    {
    	int n,m,i,j,k,x,y,c,flag=0,ch=-1;
    	int a[105][105],cost[105][105];
    	memset(a,0,sizeof a);
    	memset(cost,inf,sizeof cost);
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d%d",&x,&y,&c);
    		a[x][y]=a[y][x]=1;
    		cost[x][y]=cost[y][x]=c;
    	}
    	for(k=1;k<=n;k++)	
    	{
    		for(j=1;j<=n;j++)
    		{
    			for(i=1;i<=n;i++)
    			{
    				if(a[i][k]&&a[k][j])
    				{
    					a[i][j]=a[j][i]=1;
    					if(cost[i][k]+cost[k][j]<cost[i][j])
    					cost[i][j]=cost[i][k]+cost[k][j];
    				}
    			}
    		}
    	}
    	int sum=inf,sm;
    	for(i=1;i<=n;i++)
    	{
    		flag=0,sm=-1;
    		for(j=1;j<=n;j++)
    		{
    			if(i==j)continue;
    			if(a[i][j]==0)
    			{
    				flag=1;
    				break;
    			}
    			else if(a[i][j]==1)
    			{
    				if(sm<cost[i][j])
    				sm=cost[i][j];
    			}
    		}
    		if(flag==0)
    		{
    			if(sm<sum)
    			{
    				sum=sm;
    				ch=i;
    			}
    			else if(sm==sum)
    			{
    				if(i<ch)
    				ch=i;
    			}
    		}
    	}
    	if(ch==-1)
    	printf("0\n");
    	else
    	printf("%d %d\n",ch,sum);
    }

2.**[Saving James Bond - Hard Version][]**

#include <stdio.h>
    #include <queue>
    #include <stack>
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <math.h>
    using namespace std;
    int n,d,flag; 
    int vis[105],path[105];
    struct Position
    {
    	int x,y;
    }position[105];
    int firstjump(int v)
    {
        int d1 = pow(position[v].x,2);
        int d2 = pow(position[v].y,2);
        int r = (d+7.5)*(d+7.5);
        if(r >= d1 + d2) return d1+d2;
        else return 0;
    }
    /*bool firstjump(int i)
    {这个函数测试点4过不去 
    	return (sqrt(position[i].x*position[i].x+position[i].y*position[i].y))<=(d+7.5);
    }*/
    bool jump(int v,int i)
    {
    	return sqrt(fabs(position[v].x-position[i].x)*fabs(position[v].x-position[i].x) 
    	+fabs(position[v].y-position[i].y)*fabs(position[v].y - position[i].y))<=d;
    }
    bool IsSave(int v)
    {
    	return (fabs(position[v].x)>=50-d||fabs(position[v].y)>=50-d);
    }
    bool cmp(int a,int b) 
    {
        return firstjump(a)<firstjump(b);
    }
    void bfs()
    {
    	int i,b[101],last,tail;
    	queue<int>q; 
        for(i=0;i<n;i++) 
        b[i]=i;
        sort(b,b+n,cmp);
        for(i=0;i<n;i++) 
    	{
            if(firstjump(b[i])) 
    		{ 
                q.push(b[i]);
                vis[b[i]]=1;
                last=b[i];
            }
        }
        int step=2;
        while(!q.empty()) 
    	{
            int p=q.front();
            q.pop();
            if(IsSave(p)) 
    		{
                int k=1;
                stack<int> s;
                printf("%d\n",step);
                while(k<step) 
    			{
                    s.push(p);
                    p=path[p];
                    k++;
                }
                while(!s.empty()) 
    			{
                    p=s.top();
                    s.pop();
                	printf("%d %d\n",position[p].x,position[p].y);
                }
                return;
            }
            for(i=0;i<n;i++) 
    		{
                if(!vis[i]&&jump(p,i)) 
    			{
                    q.push(i);
                    path[i]=p; 
                    vis[i]=1;
                    tail=i;
                }
            }
            if(last==p) 
    		{
                step+=1;
                last=tail;
            }
        }
        if(q.empty()) 
    	printf("0\n");
    }
    int main()
    {
    	int i;
    	memset(vis,0,sizeof vis);
    	scanf("%d %d",&n,&d);
    	for(i=0;i<n;i++)
    	scanf("%d %d",&position[i].x,&position[i].y);	
    	if(d>=42.5) 
     	printf("1\n");
        else
    	bfs();
    }

**3.[旅游规划][Link 2]**

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int ma[505][505],val[505][505];
    int main()
    {
    	int n,m,s,d,i,j,k,x,y,z,p;
    	memset(ma,inf,sizeof ma);
    	memset(val,inf,sizeof val);
    	scanf("%d%d%d%d",&n,&m,&s,&d);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d%d%d",&x,&y,&z,&p);
    		ma[x][y]=ma[y][x]=z;
    		val[x][y]=val[y][x]=p;
    	}
    	for(k=0;k<n;k++)
    	{
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				if(ma[i][j]>ma[i][k]+ma[k][j])
    				{
    					ma[i][j]=ma[i][k]+ma[k][j];
    					val[i][j]=val[i][k]+val[k][j];
    				}
    				else if(ma[i][j]==ma[i][k]+ma[k][j])
    				{
    					if(val[i][j]>val[i][k]+val[k][j])
    					val[i][j]=val[i][k]+val[k][j];
    				}
    			}
    		}
    	}
    	printf("%d %d\n",ma[s][d],val[s][d]);
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1151317971049771008
[Saving James Bond - Hard Version]: https://pintia.cn/problem-sets/1134360184290500608/problems/1151317971049771009
[Link 2]: https://pintia.cn/problem-sets/1134360184290500608/problems/1151317971049771010