【洛谷P1359 】租用游艇多种写法

墨蓝 2023-08-17 16:26 100阅读 0赞

一.dijkstra模板

#include<iostream>
    #include<cstring>
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int maxn=205;
    bool visit[maxn];
    int dis[maxn];
    int map_dis[maxn][maxn];
    int n,m;
    int dijkstra(int s,int t)
    {
        memset(visit,false,sizeof(visit));
        for(int i=1;i<=n;i++)//初始化 
        dis[i]=map_dis[s][i];
        dis[s]=0;
        visit[s]=true;
        for(int i=1;i<n;i++)//求最小值
        {
            int v;
            int minx=inf;
            for(int j=1;j<=n;j++)
            if(!visit[j]&&dis[j]<minx)
            {
                minx=dis[j];
                v=j;
            }
            if(minx==inf)//无最小值 
            return -1;
            //更新
            visit[v]=true;
            for(int u=1;u<=n;u++)
            if(!visit[u]&&dis[u]>map_dis[v][u]+dis[v] )
            dis[u]=map_dis[v][u]+dis[v];
         } 
         return dis[t];
    }
    int main()
    {
            cin>>n;
           memset(map_dis,inf,sizeof(map_dis));
            for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++)
            {
            int w; cin>>w;
            map_dis[i][j]=w;
            }
            }
            cout<<dijkstra(1,n)<<endl;
    }

二.搜索

#include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #define LL long long
    using namespace std;
    #define inf 0x3f3f3f3f
    int n,map[201][201],ans=inf;
    void dfs(int t,int step)
    {
        if(step >=ans)//剪枝 
            return;
        if(t == n) {
            ans=min(ans,step);
            return; //回溯 
        }
        for(int i = t + 1 ; i <= n ; ++ i)//挨个枚举下游各个点 
            dfs(i,step + map[t][i]);
    }
    int main()
    {
        scanf("%d",&n);
        for(int i = 1 ; i < n ; ++ i)   //进行存图 
            for(int j = i + 1 ; j <= n ; ++ j )
                scanf("%d",&map[i][j]);
        dfs(1,0);   //起点是1 
        printf("%d",ans);
        return 0;
    }

三.动规题

#include<iostream>
    #include<cstring>
    using namespace std;
    #define maxn 210
    int main(){
        int n,x;
        cin>>n;
        int dp[maxn];// //f[x]表示从1到x的距离
        memset(dp,0,sizeof(dp));
        for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            cin>>x;
            if(dp[j]==0||dp[j]>dp[i]+x) //如果j还没有到过或者到j的距离比原来短
            dp[j]=dp[i]+x;
        }
        cout<<dp[n]<<endl;
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11515243.html