2018年全国多校算法寒假训练营练习比赛（第一场）E 恋与程序员

旧城等待， 2021-12-22 08:07 177阅读 0赞

[https://www.nowcoder.com/acm/contest/67/E][https_www.nowcoder.com_acm_contest_67_E]

思路：

dfs

代码：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pb push_back
    #define mp make_pair
    #define pii pair<int,int>
    #define mem(a,b) memset(a,b,sizeof(a))
    
    const int N=105;
    const int INF=0x3f3f3f3f;
    int cnt=0;
    int head[N];
    int cost[N];
    int d[N];
    bool used[N];
    bool vis[N];
    struct edge{
        int to,w,next;
    }edge[N];
    void add_edge(int u,int v,int w){
        edge[cnt].to=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    int ans=INF,c,k;
    void dfs(int u){
    if(u==c){
            int tot=0;
            for(int i=1;i<=k;i++)if(used[i])tot+=cost[i];
            ans=min(ans,tot);
        }else{
            for(int i=head[u];~i;i=edge[i].next){
                if(!vis[edge[i].to])
                {
                    bool t=used[edge[i].w];
                    used[edge[i].w]=true;
                    vis[edge[i].to]=true;
                    dfs(edge[i].to);
                    vis[edge[i].to]=false;
                    used[edge[i].w]=t;
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,m,e,a,b,u,v;
        while(cin>>n>>m>>k>>c){
            mem(head,-1);
            mem(vis,false);
            mem(used,false); 
            cnt=0;
            while(m--){
                cin>>u>>v>>e;
                add_edge(u,v,e);
            }
            for(int i=0;i<k;i++){
                cin>>a>>b;
                cost[a]=b;
            }
            ans=INF;
            dfs(1);
            cout<<ans<<endl;
        }
        return 0; 
    } 
    /*
    6 7 5 6
    2 3 2
    4 3 3
    1 2 1
    1 5 4
    4 6 5
    1 4 2
    5 6 3
    1 100
    3 422
    2 210
    5 107
    4 38
    */

转载于:https://www.cnblogs.com/widsom/p/8325904.html

[https_www.nowcoder.com_acm_contest_67_E]: https://www.nowcoder.com/acm/contest/67/E