NOIP 2017 d2t2 70points

革命之路漫漫

第一次尝试 40points spfa

 #include <bits/stdc++.h>

 #define read read()

 using namespace std;

 inline int read

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>'') {if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+(ch-'');ch=getchar();}

     return x*f;

 }

 const int N = ;

 struct edge{

     int v,nxt,w;

 }e[N<<];

 int n,m;

 int head[N],size;

 int dis[N],vis[N],maxn = INT_MAX;

 void add(int u,int v,int w)

 {

     e[++size].v = v;

     e[size].w = w;

     e[size].nxt = head[u];

     head[u] = size;

 }

 queue<int>q;

 void spfa(int s)

 {

     memset(dis,0x3f,sizeof(dis));

     memset(head,,sizeof());

     memset(vis,,sizeof(vis));

     dis[s] = ;

     q.push(s);

     vis[s] = ;

     while(!q.empty())

     {

         int u = q.front(); q.pop(); vis[u] = ;

         for(int i = head[u]; i ; i = e[i].nxt)

         {

             int v = e[i].v, w = e[i].w;

             if(dis[v] > dis[u] + )

             {

                 dis[v] = dis[u] + ;

                 if(!vis[v])

                 {

                     q.push(v);

                     vis[v] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     freopen("treasure.in","r",stdin);

     n = read; m = read;

     int u,v,w;

     for(int i = ; i <= m; i++)

     {

         u = read; v = read; w = read;

         add(u,v,w);

         add(v,u,w);     }

     for(int i = ; i <= n; i++)

     {

         spfa(i);

         int ans = ;

         for(int i = ; i <= n; i++)

         {

             ans += dis[i] * w;

         }

         maxn = min(maxn , ans);

     }

     printf("%d",maxn);

     return ;

 }

第二次尝试 dfs

 #include <bits/stdc++.h>

 #define read read()

 using namespace std;

 const int N = ;

 int n,m;

 int cost[N][N],cnt[N];

 int head[N],size;

 int ans = INT_MAX, mincost;

 int read

 {

     int x = ; char ch = getchar();

     while(ch <  || ch > ) ch = getchar();

     while(ch >= && ch <= ) { x =  * x + ch - ; ch = getchar();}

     return x;

 }

 void dfs(int cur)//暴力枚举所有情况;

 {

     if(cur == n)

     {

         ans = min(ans,mincost);

         return;

     }

     if(mincost > ans) return;

     for(int i = ; i <= n; i++) //枚举出点;

     {

         if(!cnt[i]) continue;   //还未连通的点不能当作出点;

         for(int j = ; j <= n; j++) //枚举入点;

         {

             if(i == j || cnt[j] || cost[i][j] == 0x3f3f3f3f) continue;

             mincost += cnt[i] * cost[i][j];

             cnt[j] = cnt[i] + ;

             dfs(cur + );

             mincost -= cnt[i] * cost[i][j];

             cnt[j] = ;

         }

     }

 }

 int main()

 {

 //    freopen("treasure.in","r",stdin);

     n = read;m = read;

     memset(cost,0x3f,sizeof(cost));

     int u,v;

     for(int i = ; i <= m; i++)

     {

         u = read; v = read;

         cost[u][v] = cost[v][u] = min(read , cost[u][v]);         //细节: u-v之间可能有多条路连接, 忽略其余选最短;

     }

     for(int i = ; i <= n; i++) //枚举起点;

     {

         cnt[i] = ;

         dfs();

         cnt[i] = ;

     }

     printf("%d",ans);

     return ;

 }