249 条题解

  • 9
    @ 2017-05-07 12:42:53

    /*
    这道题有两种做法
    1.建立无向图+最短路算法,难点在于建图,读入时间之后,把能到达的点之间都连上边,跑一遍SPFA,
    边权就是出发点的点权,设最上是1号点,d[1]+w[1]就是答案
    注意,本行行尾可以到达本行及上一行的行首
    2,标程应该是动态规划吧
    f[i][j]表示第i行第j个点到目标终点(1,1)的最小时间
    则转换为数字三角形问题,但是只是多了几种走法,不断更新最小值就好了
    但是问题就来了,这样动态规划具有最优子结构吗?
    注意这是个环形走法
    答案是不成立于的,怎么说?
    我们来看一下这样一个例子,假设某个数据的第某层的时间为
    1,1,1,1,1,1
    而从下往上推上来一开始的初值f[][]分别为
    1,2,4,3,9,10
    那么我们先进行第一次同行内从左往右的更新的递推(可以看代码内的推法)
    则有更新为
    1,2,3,3,4,5
    再从右往左更新推一遍
    1,2,3,3,4,2(左端的1可以走到右端来更新了右端的时间)
    那么这样就完了吗?不,我们可以发现我们可以用新更新的2去更新推出更优的解
    则应该为
    1,2,3,3,3,2
    所以从这个样例中我们可以看出一次两边推根本的不出最优解
    为什么呢?
    我们看某次往一边推,由于是环形,所以可能从右向左推,用第一个更新了最右端的那个点
    但是最右端的那个点在更新之前已经推完了右边数的第二个点
    就是新更新的这个右端点并没有用来当作"下家"来更新别的点使别的点更优
    同理从左往右也是一样
    那么怎么办呢?
    我们可以推两遍,这样假如更新了某个端点的值,在下一次递推时一定能用来作为"下家"尝试再更新别的点
    那么这样问题就解决了
    我们总结一下做法
    首先每个点的初值为从下一层走到这一层的两个更优解
    然后我们在同层迭代递推,左推一遍右推一遍,然后再重复推一遍
    问题就解决了,so easy
    */

    DP:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int maxn=1005;
    int a[maxn][maxn];
    int f[maxn][maxn];
    int n;
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
            cin>>a[i][j];
        f[1][1]=a[1][1];//终点处就直接是该点时间
        for(int i=2;i<=n;i++)//一层一层往上推
        {
            for(int j=2;j<i;j++)//先求出从上一层推出来的最小值
                f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
            f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
            f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
            //同一层更新最优解
            for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
                f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
            f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
    
            for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
                f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
    
            for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
                f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
                f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
    
            for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
                f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                    f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
        }
        cout<<f[n][1]<<endl;
    }
    

    SSSP
    最短路很容易~
    但是建图有点麻烦~~
    因为考虑到如果从一个点往上连边的话
    会有点小麻烦(可能不存在~)
    那么我们可以从每一个点开始
    每一个可以走到它的点向他连边
    即向下找往上连
    如果是在一行的首位置或者末位置就有5种被走上来的方法
    否则四种走法
    这个需要很小心注意一个地方写错了就gg(调了半小时)
    好坑的地方就是这里的右上方=上方....
    害怕~
    然后用个等差数列求和公式求出对应的顶标就好啦~

    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int MAXn=1005;
    const int MAXN=500501;
    const int MAXM=2500001;
    const int INF=(1<<30)-1;
    struct Edge
    {
        int to,w,next;
    }e[MAXM];
    int fisrt[MAXN];//Edges
    queue<int> q;
    int d[MAXN],in[MAXN];//SPFA
    int w[MAXn][MAXn];
    int l,n,tot;
    
    inline void Add_Edge(int x,int y,int w)
    {
        e[++tot].to=y;  e[tot].w=w;
        e[tot].next=fisrt[x];   fisrt[x]=tot;
    }
    
    inline int getn(int x,int y)
    {
        return x*(x-1)/2+y;
    }
    
    void init()
    {
        memset(fisrt,-1,sizeof(fisrt));
        scanf("%d",&l); n=getn(l,l);
        for(int i=1;i<=l;i++)
            for(int j=1;j<=i;j++)
                scanf("%d",&w[i][j]);
    }
    
    void getmap()//建图从上向下建更方便
    {
        Add_Edge(2,1,w[2][1]);
        Add_Edge(3,1,w[2][2]);
        for(int i=2;i<=l;i++)
            for(int j=1;j<=i;j++)
            {
                int u=getn(i,j);
                if(j==1)
                {
                    Add_Edge(getn(i,i),u,w[i][i]);
                    Add_Edge(getn(i,j+1),u,w[i][j+1]);
                    if(i!=l)
                        Add_Edge(getn(i+1,i+1),u,w[i+1][i+1]),
                        Add_Edge(getn(i+1,j),u,w[i+1][j]),
                        Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
                }
                else    if(j==i)
                {
                    Add_Edge(getn(i,j-1),u,w[i][j-1]);
                    Add_Edge(getn(i,1),u,w[i][1]);
                    if(i!=l)
                        Add_Edge(getn(i+1,j),u,w[i+1][j]),
                        Add_Edge(getn(i+1,1),u,w[i+1][1]),
                        Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
                }
                else
                {
                    Add_Edge(getn(i,j-1),u,w[i][j-1]);
                    Add_Edge(getn(i,j+1),u,w[i][j+1]);
                    if(i!=l)
                        Add_Edge(getn(i+1,j),u,w[i+1][j]),
                        Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
                }
            }
    }
    
    void SPFA(int s)
    {
        memset(d,0x37,sizeof(d));
        q.push(s);  d[s]=0;  in[s]=1;
        while(!q.empty())
        {
            int u=q.front();    q.pop();    in[u]=0;
            for(int i=fisrt[u];i!=-1;i=e[i].next)
            {
                int& v=e[i].to; int& w=e[i].w;
                if(d[v]>d[u]+w)
                {
                    d[v]=d[u]+w;
                    if(!in[v])
                    {
                        q.push(v);
                        in[v]=1;
                    }
                }
            }
        }
        cout<<d[1]+w[1][1]<<endl;
    }
    
    int main()
    {
        init();
        getmap();
        SPFA(getn(l,1));
    }
    
    • @ 2017-08-11 13:51:20

      你的动规算法的文字说明没看的太懂,代码大概理解了。关于动规的代码我有个问题想问一下:
      为何非要在内层for循环里面从左往右、从右往左各自推两次呢?我把后两次的推导给屏蔽了,提交上去也是对的呢?
      就是这个样子:

      #include <iostream>
      #include <cstdio>
      #include <algorithm>
      #include <cstring>
      using namespace std;
      
      const int maxn=1005;
      int a[maxn][maxn];
      int f[maxn][maxn];
      int n;
      
      int main()
      {
          cin>>n;
          for(int i=1;i<=n;i++)
              for(int j=1;j<=i;j++)
              cin>>a[i][j];
          f[1][1]=a[1][1];//终点处就直接是该点时间
          for(int i=2;i<=n;i++)//一层一层往上推
          {
              for(int j=2;j<i;j++)//先求出从上一层推出来的最小值
                  f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
              f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
              f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
              //同一层更新最优解
              for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
                  f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
              f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
      
              for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
                  f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                  f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
      
              /*for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
                  f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
                  f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
      
              for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
                  f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                      f[i][1]=min(f[i][1],f[i][i]+a[i][1]);*/
          }
          cout<<f[n][1]<<endl;
      }
      
    • @ 2018-07-21 09:11:12

      @moshtian: 数据水喽。。。

  • 3
    @ 2017-08-10 16:58:12
    
    
    var f,a:array[0..1001,0..1001] of longint;
    i,j,n:longint;
    flag:boolean;
    procedure compare(x,y:longint);
    begin
    if f[x,y]+a[i,j]<f[i,j] then
    begin
    flag:=false;
    f[i,j]:=f[x,y]+a[i,j];
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do
    begin
    for j:=1 to i do read(a[i,j]);
    readln;
    end;
    fillchar(f,sizeof(f),60);
    f[1,1]:=a[1,1];
    for i:=2 to n do
    repeat
    flag:=true;
    f[i,0]:=f[i,i];f[i,i+1]:=f[i,1];
    for j:=1 to i do
    begin
    compare(i-1,j-1);
    compare(i-1,j);
    compare(i,j-1);
    compare(i,j+1);
    end;
    until flag;
    writeln(f[n,1]);
    end.
    
    
  • 2
    @ 2021-03-15 18:48:41
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
        
        class pnt{
        public:
            int x,y;
        };
        
        int n;
        int a[1<<10][1<<10];
        int vis[1<<10][1<<10],f[1<<10][1<<10];
        deque<pnt> q;
        
        void chkq(pnt next)
        {
            if (vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                q.push_back(next);
            }
        }
        void chkf(pnt now,pnt next)
        {
            if (f[now.x][now.y]+a[next.x][next.y]<f[next.x][next.y])
            {
                f[next.x][next.y]=f[now.x][now.y]+a[next.x][next.y];
                chkq(next);
            }
        }
        void main()
        {
            scanf("%d",&n);
            for (int i=0;i<n;i++)
                for (int j=0;j<=i;j++)
                    scanf("%d",&a[i][j]);
            memset(f,oo_max,sizeof(f));
            f[0][0]=a[0][0];
            pnt start;
            start.x=0,start.y=0;
            for (memset(vis,0,sizeof(vis)),vis[start.x][start.y]=1,q.clear(),q.push_back(start);!q.empty();vis[q.front().x][q.front().y]=0,q.pop_front())
            {
                pnt now=q.front();
                if (now.x<n)
                {
                    pnt next;
                    next.x=now.x,next.y=now.y+1;
                    if (next.y>next.x)
                        next.y=0;
                    chkf(now,next);
                    next.x=now.x,next.y=now.y-1;
                    if (next.y<0)
                        next.y=next.x;
                    chkf(now,next);
                    if (now.x<n-1)
                    {
                        next.x=now.x+1,next.y=now.y;
                        chkf(now,next);
                        next.x=now.x+1,next.y=now.y+1;
                        chkf(now,next);
                        if (now.y==0)
                        {
                            next.x=now.x+1,next.y=now.x+1;
                            chkf(now,next);
                        }
                        if (now.y==now.x)
                        {
                            next.x=now.x+1,next.y=0;
                            chkf(now,next);
                        }
                    }
                }
            }
            printf("%d\n",f[n-1][0]);
        }
    };
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2018-10-06 15:06:55

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define INF 0x7ffffabc
    #define MAXN 1007
    using namespace std;
    void Read(int &p)
    {
    p=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
    if(c=='-') f=-1;
    c=getchar();
    }
    while(c>='0'&&c<='9')
    p=p*10+c-'0',c=getchar();
    p*=f;
    }
    int N,mp[MAXN][MAXN],dp[MAXN][MAXN];
    void debug()
    {
    for(int i=1;i<=N;i++,putchar('\n'))
    for(int j=1;j<=i;j++)
    if(dp[i][j])printf("%d ",dp[i][j]);
    }
    int main()
    {
    Read(N);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=i;j++)
    Read(mp[i][j]);
    dp[1][1]=mp[1][1];
    for(int i=2;i<=N;i++)
    {
    for(int j=2;j<i;j++)
    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+mp[i][j];
    dp[i][1]=min(dp[i-1][1],dp[i-1][i-1])+mp[i][1];
    dp[i][i]=min(dp[i-1][i-1],dp[i-1][1])+mp[i][i];
    for(int t=1;t<=2;t++)
    {
    for(int j=i-1;j>=1;j--)
    dp[i][j]=min(dp[i][j],dp[i][j+1]+mp[i][j]);
    dp[i][i]=min(dp[i][i],dp[i][1]+mp[i][i]);

    for(int j=2;j<=i;j++)
    dp[i][j]=min(dp[i][j],dp[i][j-1]+mp[i][j]);
    dp[i][1]=min(dp[i][1],dp[i][i]+mp[i][1]);
    }
    }
    printf("%d\n",dp[N][1]);
    return 0;
    }

  • 1
    @ 2018-10-06 15:06:35

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define INF 0x7ffffabc
    #define MAXN 1007
    using namespace std;
    void Read(int &p)
    {
    p=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
    if(c=='-') f=-1;
    c=getchar();
    }
    while(c>='0'&&c<='9')
    p=p*10+c-'0',c=getchar();
    p*=f;
    }
    int N,mp[MAXN][MAXN],dp[MAXN][MAXN];
    void debug()
    {
    for(int i=1;i<=N;i++,putchar('\n'))
    for(int j=1;j<=i;j++)
    if(dp[i][j])printf("%d ",dp[i][j]);
    }
    int main()
    {
    Read(N);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=i;j++)
    Read(mp[i][j]);
    dp[1][1]=mp[1][1];
    for(int i=2;i<=N;i++)
    {
    for(int j=2;j<i;j++)
    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+mp[i][j];
    dp[i][1]=min(dp[i-1][1],dp[i-1][i-1])+mp[i][1];
    dp[i][i]=min(dp[i-1][i-1],dp[i-1][1])+mp[i][i];
    for(int t=1;t<=2;t++)
    {
    for(int j=i-1;j>=1;j--)
    dp[i][j]=min(dp[i][j],dp[i][j+1]+mp[i][j]);
    dp[i][i]=min(dp[i][i],dp[i][1]+mp[i][i]);

    for(int j=2;j<=i;j++)
    dp[i][j]=min(dp[i][j],dp[i][j-1]+mp[i][j]);
    dp[i][1]=min(dp[i][1],dp[i][i]+mp[i][1]);
    }
    }
    printf("%d\n",dp[N][1]);
    return 0;
    }

  • 1
    @ 2017-11-07 07:57:01

    乱打了一个

    #include<cstdio>
    #include<iostream>
    #define MAX_N 1005
    using namespace std;
    
    int n,map[MAX_N][MAX_N],f[MAX_N][MAX_N],k1[MAX_N][MAX_N],k2[MAX_N][MAX_N];
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                scanf("%d",&map[i][j]);
        f[1][1]=map[1][1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(j==1||j==i) f[i][j]=min(f[i-1][i-1],f[i-1][1])+map[i][j];
                else f[i][j]=min(f[i-1][j],f[i-1][j-1])+map[i][j];
            }
            k1[i][1]=f[i][1];k2[i][i]=f[i][i];
            for(int j=2;j<=i;j++)
                k1[i][j]=min(k1[i][j-1]+map[i][j],f[i][j]);
            k1[i][1]=min(k1[i][1],k1[i][i]+map[i][1]);
            for(int j=i-1;j>=1;j--)
                k2[i][j]=min(k2[i][j+1]+map[i][j],f[i][j]);
            k2[i][i]=min(k2[i][i],k2[i][1]+map[i][i]);
            for(int j=1;j<=i;j++)
                f[i][j]=min(f[i][j],min(k1[i][j],k2[i][j]));
        }
        cout<<f[n][1];
        return 0;
    * }
    
  • 1
    @ 2017-05-12 14:24:30

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include<algorithm>
    using namespace std;

    const int maxn = 1002;
    int hill[maxn][maxn];
    int dp[maxn][maxn];
    int inf = 1000000000;

    int main(){
    int n;
    cin >> n;
    for(int p = 1; p <= n; p++){
    for(int q = 1; q <= p; q++){
    cin >> hill[p][q];
    }
    }
    dp[n][1] = hill[n][1];
    int left = 0;
    int right = 0;
    for(int i = 3; i <= n; i++){
    right += hill[n][i];
    }
    for(int i = 2; i < n; i++){
    dp[n][i] = min(left, right) + hill[n][1] + hill[n][i];
    left += hill[n][i];
    right -= hill[n][i + 1];
    }
    dp[n][n] = dp[n][1] + hill[n][n];
    for(int i = n - 1; i > 1; i--){
    for(int p = 1; p <= i; p++){
    dp[i][p] = min(dp[i + 1][p], dp[i + 1][p + 1]);
    if(p == 1)dp[i][p] = min(dp[i][p], dp[i + 1][i + 1]);
    if(p == i)dp[i][p] = min(dp[i][p], dp[i + 1][1]);
    dp[i][p] += hill[i][p];
    }
    int min_ = inf;
    int pos;
    for(int p = 1; p <= i; p++){
    if(min_ > dp[i][p]){
    pos = p;
    min_ = dp[i][p];
    }
    }
    for(int p = 1; p < n; p++){
    int h = p + pos;
    int fa = h - 1;
    if(h > i) h -= i;
    if(fa > i) fa -= i;
    dp[i][h] = min(dp[i][h], dp[i][fa] + hill[i][h]);
    }
    for(int p = 1; p < n; p++){
    int h = pos - p;
    int fa = h + 1;
    if(h < 1) h += i;

    if(fa < 1) fa += i;
    dp[i][h] = min(dp[i][h], dp[i][fa] + hill[i][h]);
    }
    }
    dp[1][1] = min(dp[2][1], dp[2][2]) + hill[1][1];
    cout << dp[1][1];
    }

  • 1
    @ 2017-05-05 17:08:42

    艹了个DJ
    #1 Accepted 19ms 5.328MiB
    #2 Accepted 13ms 5.75MiB
    #3 Accepted 6ms 5.625MiB
    #4 Accepted 4ms 5.391MiB
    #5 Accepted 17ms 6.0MiB
    #6 Accepted 16ms 5.703MiB
    #7 Accepted 10ms 5.0MiB
    #8 Accepted 19ms 7.055MiB
    #9 Accepted 22ms 6.25MiB
    #10 Accepted 31ms 8.0MiB

    #include<iostream>
    #include<memory.h>
    using namespace std;

    const int MAX = 1002;
    const int INF = 1000000;

    int T[MAX][MAX];
    int dp[MAX][MAX];
    int pre[4][2] = { { 0,-1 },{ 0,1 },{ -1,0 },{ -1,-1 } };

    int main() {
    int n;
    cin >> n;
    int i, j, k;
    for (i = 1; i <= n; i++) for (j = 0; j<i; j++) cin >> T[i][j];
    memset(dp, INF, sizeof(dp));
    dp[1][0] = T[1][0]; int ti, tj; int tdp; bool flag;
    for (i = 2; i <= n; i++) {
    do {
    flag = false;
    for (j = 0; j<i; j++) {
    for (k = 0; k<4; k++) {
    ti = i + pre[k][0]; tj = (j + pre[k][1] + ti) % ti;
    tdp = dp[ti][tj] + T[i][j];
    if (tdp<dp[i][j]) {
    flag = true;
    dp[i][j] = tdp;
    }
    }
    }
    } while (flag);

    }
    cout << dp[n][0] << endl;
    return 0;
    }

  • 1
    @ 2017-01-17 16:42:55

    最短路……

  • 1
    @ 2016-08-28 22:46:40

    一开始把数组dist和vis定义成maxn了,结果耗了2h才发现应该是maxn*maxn.......
    #include <cstdio>
    #include <cstdlib>
    #include <queue>
    #define rep(i, x, y) for (int i = x; i <= y; ++i)
    #define inf (1 << 30)

    using namespace std;

    const int maxn = 1005;
    int n, m;

    struct Node {
    int nextNode, length;
    Node *next;
    } *N[maxn * maxn], pool[maxn * maxn * 2];
    struct Node2 {
    int num, val;
    bool operator < (const Node2 &xx) const {
    return val > xx.val;
    }
    };
    int pcnt;
    inline void addedge(int x, int y, int l) {
    Node *p = &pool[++pcnt];
    *p = (Node){y, l, N[x]};
    N[x] = p;
    }
    int dist[maxn * maxn], vis[maxn * maxn];
    inline void Dijkstra(int k) {
    rep(i, 1, m) dist[i] = inf;
    dist[k] = 0;
    priority_queue <Node2> q;
    q.push((Node2){k, 0});
    while (!q.empty()) {
    int x = q.top().num;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (Node *p = N[x]; p; p = p->next) {
    if (dist[p->nextNode] > dist[x] + p->length) {
    dist[p->nextNode] = dist[x] + p->length;
    q.push((Node2){p->nextNode, dist[p->nextNode]});
    }

    }
    }
    }
    int main(int argc, const char *argv[]) {
    scanf("%d", &n);
    int val, ecnt = 0;
    int ad;
    rep(i, 1, n) {
    scanf("%d", &val);
    if (i == 1) ad = val;
    ++ecnt;
    addedge(ecnt, ecnt - i + 1, val);
    addedge(ecnt, ecnt - 1, val);
    addedge(ecnt, ecnt + i - 1, val);
    addedge(ecnt, ecnt + 1, val);
    rep(j, 2, i - 1) {
    scanf("%d", &val);
    ++ecnt;
    addedge(ecnt, ecnt - i + 1, val);
    addedge(ecnt, ecnt - i, val);
    addedge(ecnt, ecnt - 1, val);
    addedge(ecnt, ecnt + 1, val);
    }
    if (i == 1) continue;
    scanf("%d", &val);
    ++ecnt;
    addedge(ecnt, ecnt - i, val);
    addedge(ecnt, ecnt - 2 * i + 2, val);
    addedge(ecnt, ecnt - 1, val);
    addedge(ecnt, ecnt - i + 1, val);
    }
    m = ecnt;
    Dijkstra(n * (n - 1) / 2 + 1);
    printf("%d\n", dist[1] + ad);
    return 0;
    }

    • @ 2016-12-16 09:12:25

      最短路,很猥琐的样子

  • 1
    @ 2016-08-17 09:55:41

    SPFA
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define xx first
    #define yy second
    using namespace std;
    pair<int,int> s[1000003];
    int l,r,n,ans[1003][1003],map[1003][1003];
    int x[4]={-1,-1,0,0},y[4]={-1,0,-1,+1};
    int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=i;j++)
    scanf("%d",&map[i][j]);
    memset(ans,63,sizeof(ans));
    l=r=1;s[1].xx=n;s[1].yy=1;ans[n][1]=map[n][1];
    while (l<=r){
    pair<int,int>now=s[l];
    for (int i=0;i<4;i++){
    int X=now.xx+x[i],Y=now.yy+y[i];
    if (Y==0)Y=X;if (Y>X)Y=1;
    if (ans[X][Y]>ans[now.xx][now.yy]+map[X][Y]){
    ans[X][Y]=ans[now.xx][now.yy]+map[X][Y];
    s[++r]=make_pair(X,Y);
    }
    }
    l++;
    }
    printf("%d\n",ans[1][1]);
    return 0;
    }

  • 1
    @ 2016-08-01 23:29:25

    #include<iostream>
    #include<cstdlib>
    #include<cstdio>
    using namespace std;
    int n[1002][1002];
    int e[1002][1002];
    int main()
    {
    int k,j,m,flag;
    cin>>k;
    for(j=1;j<=k;j++)
    for(m=1;m<=j;m++)
    {
    scanf("%d",&n[j][m]);
    e[j][m]=99999;}
    e[1][0]=e[1][1]=e[1][2]=n[1][1];

    for(j=2;j<=k;j++)
    {
    while(1)
    {
    flag=0;
    e[j][0]=e[j][j];
    e[j][j+1]=e[j][1];// 两行用作特殊走法
    for(m=1;m<=j;m++)
    {
    if(e[j][m]>e[j][m-1]+n[j][m])

    {e[j][m]=e[j][m-1]+n[j][m];flag=1;}
    if(e[j][m]>e[j][m+1]+n[j][m])

    {e[j][m]=e[j][m+1]+n[j][m];flag=1;}

    if(e[j][m]>e[j-1][m-1]+n[j][m])

    {e[j][m]=e[j-1][m-1]+n[j][m];flag=1;}
    if(e[j][m]>e[j-1][m]+n[j][m])

    {e[j][m]=e[j-1][m]+n[j][m];flag=1;}

    }
    if(flag==0)
    break;
    }
    }
    cout<<e[k][1]<<endl;
    system("pause");
    }

  • 1
    @ 2016-06-10 13:57:21
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <queue>
    #include <algorithm>
    using namespace std;
    int map[1000+5][1000+5];
    #define N 500500
    #define M 2502500
    int n;
    int head[N],dis[N],vis[N];
    struct graph
    {
        int next, to, val;
        graph() {}
        graph(int _next, int _to, int _val)
        : next(_next), to(_to), val(_val) {}
    } edge[M];
    int tt=1;
    inline void add(int x, int y, int z)
    {
        static int cnt = 0;
        edge[++cnt] = graph(head[x], y, z);
        head[x] = cnt;
    }
    inline int read()
    {
        int x = 0, f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
        return x * f;
    }
    void solve(int Line,int Row)
    {
        if(Line==1&&Row==1)
        {
            add(1,2,map[2][1]);
            add(1,3,map[2][2]);
            return ;
        }
        if(Row==1)
        {
            add(tt,tt+Line-1,map[Line][Line]);
            add(tt,tt+Line,map[Line+1][1]);
            add(tt,tt+1,map[Line][2]);
            add(tt,tt+Line+1,map[Line+1][2]);
            add(tt,tt+2*Line,map[Line+1][Line+1]);
            return;
        }
        else if(Row==Line)
        {
            add(tt,tt-Line+1,map[Line][1]);
            add(tt,tt+Line,map[Line+1][Row]);
            add(tt,tt+Line+1,map[Line+1][Row+1]);
            add(tt,tt+1,map[Line+1][1]);
            add(tt,tt-1,map[Line][Row-1]);
            return;
        }
        else
        {
            add(tt,tt-1,map[Line][Row-1]);
            add(tt,tt+1,map[Line][Row+1]);
            add(tt,tt+Line,map[Line+1][Row]);
            add(tt,tt+Line+1,map[Line+1][Row+1]);
            return;
        }
    }
    queue <int >Q;
    void spfa()
    {
        memset(dis,0x3f,sizeof dis);
        int start=1,end=n*(n-1)/2;end++;
        dis[start]=0;vis[start]=true;
        Q.push(start);
        while(!Q.empty())
        {
            int t=Q.front();
            Q.pop();
            vis[t]=false;
            for(int i=head[t];i;i=edge[i].next)
            {
                int tmp=edge[i].val;
                if(tmp+dis[t]<dis[edge[i].to])
                {   
                    dis[edge[i].to]=tmp+dis[t];
                    if(!vis[edge[i].to])
                    {
                        vis[edge[i].to]=true;
                        Q.push(edge[i].to);
                    }
                }
            }
        }
        printf("%d",dis[end]+map[1][1]);
    }
    int main()
    {
        freopen("PE.in", "r", stdin);
        freopen("PE.out", "w", stdout);
        memset(map,0x3f,sizeof map);
        cin>>n;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=i;++j)
                map[i][j]=read();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=i;++j)
            {
                solve(i,j);
                tt++;
            }
        //DFS(1);
        spfa();
    }
    

    最短路无脑来一发就行了 注意建图的一些细节

  • 0
    @ 2017-09-16 16:00:45
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int maxn=1005;
    int a[maxn][maxn];
    int f[maxn][maxn];
    int n;
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
            cin>>a[i][j];
        f[1][1]=a[1][1];//终点处就直接是该点时间
        for(int i=2;i<=n;i++)//一层一层往上推
        {
            for(int j=2;j<i;j++)//先求出从上一层推出来的最小值
                f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
            f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
            f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
            //同一层更新最优解
            for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
                f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
            f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
    
            for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
                f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
    
            for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
                f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
                f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
    
            for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
                f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                    f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
        }
        cout<<f[n][1]<<endl;
    }
    
  • 0
    @ 2015-10-28 17:18:41

    最短路+1
    难点是构图,需要进行一些坑爹的代数运算,还要把点权移到边权上去。由于没有负权回路,故最短路总能输出答案。

    #include <stdio.h>
    #include <limits.h>

    struct edge{
    int to, value;
    } E[600000][4];
    int numEdge[600000];
    int queue[1000000];
    int dist[600000];
    short using[600000];

    void addEdge(int from, int to, int value){
    E[from][numEdge[from]].to = to;
    E[from][numEdge[from]].value = value;
    numEdge[from]++;
    }
    int minPath(int source, int sink, int numV){
    int head = 0, tail = 1, i, u;
    for(i=0; i<=numV; i++){
    dist[i] = LONG_MAX;
    using[i] = 0;
    }
    queue[0] = source;
    dist[source] = 0;
    using[source] = 1;
    while(head < tail){
    u = queue[head];
    using[u] = 0;
    for(i=0; i<numEdge[u]; i++){
    if(dist[u] + E[u][i].value < dist[E[u][i].to]){
    dist[E[u][i].to] = dist[u] + E[u][i].value;
    if(!using[E[u][i].to]){
    using[E[u][i].to] = 1;
    queue[tail] = E[u][i].to;
    tail++;
    }
    }
    }
    head++;
    }
    return dist[sink];
    }
    int main(){
    int height, i, j, value, numV;
    scanf("%d", &height);
    for(i=0; i<600000; i++)
    numEdge[i] = 0;
    numV = 0;
    for(i=1; i<=height; i++){
    for(j=0; j<i; j++){
    scanf("%d", &value);
    addEdge(numV+j, numV+(j+i-1)%i, value); //left
    addEdge(numV+j, numV+(j+i+1)%i, value); //right
    if(i > 1){
    addEdge(numV+j, numV-i+1+(j+i-2)%(i-1), value); //left-up
    addEdge(numV+j, numV-i+1+(j+i-1)%(i-1), value); //right-up
    }else{
    addEdge(numV+j, height*(height+1)/2, value); //top
    }
    }
    numV += i;
    }
    printf("%d\n", minPath(numV-height, height*(height+1)/2, numV+1));
    return 0;
    }

    • @ 2016-03-06 10:32:19

      其实就是搞数学... 我用的是数列求和来搞 点的编号... 然后*Dijkstra*要优先队列优化...

  • 0
    @ 2015-10-25 11:01:47

    ###Block code
    最短路秒杀~!~!~!~!~!~!

  • 0
    @ 2015-08-15 14:48:36

    测试数据 #0: Accepted, time = 15 ms, mem = 8360 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 8356 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 8360 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 8360 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 8360 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 8356 KiB, score = 10
    测试数据 #6: Accepted, time = 2 ms, mem = 8356 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 8360 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 8356 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 8360 KiB, score = 10
    Accepted, time = 168 ms, mem = 8360 KiB, score = 100

    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    #include <algorithm>
    #include <string.h>
    #include <queue>
    using namespace std;
    typedef long long LL;
    const int N = 1001;
    const int M = 3850;
    int n,m;
    int s[N][N];
    int dp[N][N];
    int main()
    {
    while(scanf("%d",&n) == 1)
    {
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
    scanf("%d",&s[i][j]);
    dp[n][0] = 0;
    for(int i = n; i >= 1; i--)
    {
    if(i == n)
    {
    for(int j = 1; j <= i; j++)
    {
    dp[i][j] = dp[i][j-1] + s[i][j];
    }
    continue;
    }
    for(int j = 1; j <= i; j++)
    {

    if(j == 1)
    dp[i][j] = min(min(dp[i+1][j],dp[i+1][j+1]),dp[i+1][i+1])+s[i][j];
    else if(j == i)
    dp[i][j] = min(min(dp[i+1][j],dp[i+1][j+1]),dp[i+1][1])+s[i][j];
    else
    dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + s[i][j];
    }
    dp[i][1] = min(dp[i][1],dp[i][i]+s[i][1]); //没有这里第六个数据WA了
    for(int j = 2; j <= i; j++)
    dp[i][j] = min(dp[i][j],dp[i][j-1] + s[i][j]);
    for(int j = i-1; j >= 1; j--)
    dp[i][j] = min(dp[i][j],dp[i][j+1] + s[i][j]);
    }
    printf("%d\n",dp[1][1]);
    }
    }

  • 0
    @ 2015-07-22 19:11:38

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int map[1010][1010];
    int time[1010][1010];
    int main()
    {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
    scanf("%d",&map[i][j]);

    time[1][1]=map[1][1];
    for(int i=2;i<=n;i++)
    {
    for(int j=2;j<i;j++)
    time[i][j]=min(time[i-1][j],time[i-1][j-1])+map[i][j];
    time[i][1]=min(time[i-1][1],time[i-1][i-1])+map[i][1];
    time[i][i]=min(time[i-1][i-1],time[i-1][1])+map[i][i];

    for(int k=i-1;k>0;k--)
    time[i][k]=min(time[i][k],time[i][k+1]+map[i][k]);
    time[i][i]=min(time[i][i],time[i][1]+map[i][i]);

    for(int l=2;l<=i;l++)
    time[i][l]=min(time[i][l],time[i][l-1]+map[i][l]);
    time[i][1]=min(time[i][1],time[i][i]+map[i][1]);

    for(int k=i-1;k>0;k--)
    time[i][k]=min(time[i][k],time[i][k+1]+map[i][k]);
    time[i][i]=min(time[i][i],time[i][1]+map[i][i]);

    for(int l=2;l<=i;l++)
    time[i][l]=min(time[i][l],time[i][l-1]+map[i][l]);
    time[i][1]=min(time[i][1],time[i][i]+map[i][1]);
    }
    printf("%d",time[n][1]);
    }

  • 0
    @ 2014-08-06 21:28:57

    没动脑子直接写程序的代码长度……
    const
    tot=1000000;
    var
    map,num:array[1..1000,1..1000] of longint;
    pi,ps,w,pb:array[1..3000000] of longint;
    p,st,kk,i,j,k,m,n:longint;
    d,q:array[1..1000000] of longint;
    v:array[1..1000000] of 0..1;
    begin
    readln(n);
    k:=0;
    for i:=1 to n do
    for j:=1 to i do
    begin
    inc(k);
    read(map[i][j]);
    num[i][j]:=k;
    end;
    fillchar(pi,sizeof(pi),0);
    fillchar(ps,sizeof(ps),0);
    k:=0;
    for i:=n downto 2 do
    begin
    for j:=1 to i do
    begin
    inc(k);
    ps[k]:=pi[num[i][j]];
    pi[num[i][j]]:=k;
    if j=i then begin
    pb[k]:=num[i][1];w[k]:=map[i][1];end
    else begin pb[k]:=num[i][j+1];w[k]:=map[i][j+1];end;

    inc(k);
    ps[k]:=pi[num[i][j]];
    pi[num[i][j]]:=k;
    if j=1 then begin
    pb[k]:=num[i][i];w[k]:=map[i][i];end
    else begin pb[k]:=num[i][j-1];w[k]:=map[i][j-1];end;

    inc(k);
    ps[k]:=pi[num[i][j]];
    pi[num[i][j]]:=k;
    if j=i then begin
    pb[k]:=num[i-1][1];w[k]:=map[i-1][1];end
    else begin pb[k]:=num[i-1][j];w[k]:=map[i-1][j];end;

    inc(k);
    ps[k]:=pi[num[i][j]];
    pi[num[i][j]]:=k;
    if j=1 then begin
    pb[k]:=num[i-1][i-1];w[k]:=map[i-1][i-1];end
    else begin pb[k]:=num[i-1][j-1];w[k]:=map[i-1][j-1];end;
    end;
    end;

    m:=n*(n+1) div 2;
    fillchar(v,sizeof(v),0);
    fillchar(q,sizeof(q),0);
    for i:=1 to m do d[i]:=maxlongint;
    st:=num[n][1];d[st]:=0;
    q[1]:=st;v[st]:=1;p:=1;k:=1;

    while true do
    begin
    kk:=k;
    repeat
    j:=pi[q[p]];
    while j<>0 do
    begin
    if d[pb[j]]>d[q[p]]+w[j] then
    begin
    d[pb[j]]:=d[q[p]]+w[j];
    if v[pb[j]]=0 then
    begin
    inc(kk);
    if kk>tot then kk:=1;
    q[kk]:=pb[j];
    v[pb[j]]:=1;
    end;
    end;
    j:=ps[j];
    end;
    v[q[p]]:=0;
    inc(p);
    if p>tot then p:=1;
    until k=p;

    if kk=k then break;
    k:=kk;
    inc(p);
    if p>tot then p:=1;
    end;

    writeln(d[1]+map[n][1]);
    end.

  • 0
    @ 2014-03-15 22:08:43

    var f,a:array[0..1001,0..1001] of longint;
    i,j,n:longint;
    flag:boolean;
    procedure compare(x,y:longint);
    begin
    if f[x,y]+a[i,j]<f[i,j] then
    begin
    flag:=false;
    f[i,j]:=f[x,y]+a[i,j];
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do
    begin
    for j:=1 to i do read(a[i,j]);
    readln;
    end;
    fillchar(f,sizeof(f),60);
    f[1,1]:=a[1,1];
    for i:=2 to n do
    repeat
    flag:=true;
    f[i,0]:=f[i,i];f[i,i+1]:=f[i,1];
    for j:=1 to i do
    begin
    compare(i-1,j-1);
    compare(i-1,j);
    compare(i,j-1);
    compare(i,j+1);
    end;
    until flag;
    writeln(f[n,1]);
    end.
    总算看着题解过了……

信息

ID
1006
难度
7
分类
动态规划 点击显示
标签
递交数
8684
已通过
1991
通过率
23%
被复制
11
上传者