[最短路]uva 12295 Optimal Symmetric Paths

/**
        
 uva 12295 Optimal Symmetric Paths__DP        
         正解，最短路
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define N 1005
#define INF 1000000000LL
#define MOD 1000000009LL

struct node
{
    int d,x,y;
    node(int a = 0,int b = 0,int c = 0)
    {
        x = a;
        y = b;
        d = c;
    }
};
bool operator<(node a,node b)
{
    return a.d > b.d;
}

#define MK node
__int64 d[N][N],ds[N][N];

int n,mat[N][N];
bool vis[N][N];
node p,pt;
int move[][2]= {0,1,1,0,0,-1,-1,0};
int ok(int x,int y)
{
    return x >= 0 && x < n && y >= 0 && y < n && x >= y ;
}
void dij()
{
    int i,j;
    for(i = 0; i < n; ++i)
        for(j = 0;j < n; ++j)
            d[i][j] = INF;
    memset(vis,0,sizeof(vis));
    int x = n - 1, y = 0;
    d[x][y] = mat[x][y];
    priority_queue< node > que;
    que.push(MK(x,y,d[x][y]));
    int dd;
    int px,py;
    while(!que.empty())
    {
        p = que.top();
        que.pop();
        x = p.x;
        y = p.y;
        if(vis[x][y])
            continue;
        vis[x][y] = 1;
        dd = p.d;
        for( i = 0; i < 4; ++i)
        {
            px = x + move[i][0];
            py = y + move[i][1];
            if(!ok(px,py))
                continue;

            if(d[px][py] - dd> mat[px][py])
            {
                d[px][py] = dd + mat[px][py];
                que.push(MK(px,py,d[px][py]));
            }
        }
    }
}
int dfs(int x,int y)
{
    if(ds[x][y])
        return ds[x][y];
    int res  = 0,px,py;
    for(int i = 0; i < 4;++i)
    {
        px = x + move[i][0];
        py = y + move[i][1];
        if(!ok(px,py))
            continue;
        if(d[px][py] + mat[x][y] == d[x][y])
                res = (res + dfs(px,py)) % MOD;
    }
    return ds[x][y] = res;
}
int main()
{
   // freopen("1.std.in","r",stdin);
  //  freopen("1.out","w",stdout);
    int i,j;
    while(scanf("%d",&n) != EOF && n)
    {
        for(i = n - 1; i >= 0; --i)
            for(j = 0; j < n; ++j)
                scanf("%d",&mat[i][j]);
        for(i = n - 1; i > 0; --i)
            for(j = 0;j < i; ++j)
                mat[i][j] += mat[j][i];
        dij();
        __int64 minn  = INF,sum = 0LL;
        for(i = 0; i < n; ++i)
        {
            if(d[i][i] < minn)
                minn = d[i][i];
        }

        memset(ds,0,sizeof(ds));
        ds[n-1][0] = 1;
        int x,y,k,cnt = 0;

        memset(vis,0,sizeof(vis));
        ds[n-1][0] = 1;
        for(i = 0; i < n; ++i)
            if(ds[i][i] == 0)
                dfs(i,i);
        for(i = 0; i < n; ++i)
            if(d[i][i] == minn)
                sum = (sum + ds[i][i]) % MOD;
        printf("%I64d\n",sum);
    }
    return 0;
}
/**
開始很挫的一代碼，priority_queue沒弄好 比較，一直WA，還誤以為pair有問題。

*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define N 505
#define INF 100000000
#define MOD 1000000009
#define MK make_pair
//#define Pii pair<int,pair<int,int> >
typedef pair<int,pair<int,int> > Pii;
int d[N][N],ds[N][N];
int n,mat[N][N],vis[N][N];
Pii p,pt;
int move[][2]= {0,1,1,0,0,-1,-1,0};
int ok(int x,int y)
{
    return x >= 0 && x < n && y >= 0 && y < n && x >= y ;
}

void dij()
{
    int i,j;
    for(i = 0; i < n; ++i)
        for(j = 0;j < n; ++j)
            d[i][j] = INF;
    memset(vis,0,sizeof(vis));
    int x = n - 1, y = 0;
    d[x][y] = mat[x][y] + mat[y][x];
    priority_queue<Pii,vector<Pii> ,greater<Pii> > que;
    que.push(MK(d[x][y],MK(x,y)));
    int dd;
    int px,py;
    while(!que.empty())
    {
        p = que.top();
        que.pop();
        x = p.second.first;
        y = p.second.second;
        dd = p.first;
      //  printf("..%d\n",dd);
        if(vis[x][y])
            continue;
        vis[x][y] = 1;
        for( i = 0; i < 4; ++i)
        {
            px = x + move[i][0];
            py = y + move[i][1];
            if(!ok(px,py))
                continue;
            if(px != py)
            {
                if(d[px][py] > dd + mat[px][py] + mat[py][px])
                {
                    d[px][py] = dd + mat[px][py] + mat[py][px];
                    que.push(MK(d[px][py],MK(px,py)));
                   // printf("..=%d,%d,%d;%d\n",px,py,d[px][py],que.size());
                }
            }
            else
            {
                if(d[px][py] > dd + mat[py][px])
                {
                    d[px][py] = dd + mat[py][px];
                    que.push(MK(d[px][py],MK(px,py)));
                   // printf("..=%d,%d,%d;%d\n",px,py,d[px][py],que.size());
                }
            }
        }
    }
}
Pii ss[N * N];
int main()
{
 //   freopen("1.std.in","r",stdin);
 //   freopen("12.out","w",stdout);
    int i,j;
    while(scanf("%d",&n) != EOF && n)
    {
        for(i = n-1; i >= 0; --i)
            for(j = 0; j < n; ++j)
                scanf("%d",&mat[i][j]);
        dij();

        int minn  = INF,sum = 0;
        for(i = 0; i < n; ++i)
        {
            if(d[i][i] < minn)
                minn = d[i][i];
        }

        memset(ds,0,sizeof(ds));
        ds[n-1][0] = 1;
        int x,y,k,cnt = 0;
        priority_queue<Pii,vector<Pii> ,greater<Pii> > que;
        p = MK(d[n-1][0],MK(n-1,0));
        que.push(p);
        memset(vis,0,sizeof(vis));
        vis[n-1][0] = 1;
        while(!que.empty())
        {
            p = que.top();
            que.pop();

            i = p.second.first;
            j = p.second.second;
            for(k = 0; k < 4; ++k)
            {
                x = i + move[k][0];
                y = j + move[k][1];
                //if(x == 0 && y == 0)
                if(!ok(x,y))
                    continue;
                if(x == y)
                {
                    if(d[x][y] == d[i][j] + mat[x][y])
                    {
                        ds[x][y] = (ds[i][j] + ds[x][y]) % MOD;
                        if(!vis[x][y])
                        {
                            que.push(MK(d[x][y],MK(x,y)));
                            vis[x][y] = 1;
                        }

                    }

                }
                else
                {
                    if(d[x][y] == d[i][j] + mat[x][y] + mat[y][x])
                    {
                        ds[x][y] = (ds[i][j] + ds[x][y]) % MOD;
                        if(!vis[x][y])
                        {
                            que.push(MK(d[x][y],MK(x,y)));
                            vis[x][y] = 1;
                        }
                    }
                }
            }
        }
        for(i = 0; i < n; ++i)
            if(d[i][i] == minn)
                sum = (sum + ds[i][i]) % MOD;
        printf("%d\n",sum);
    }
    return 0;
}

/**
uva 12295 竟然可以dp水過。
*/
#include<stdio.h>

#define N 101
#define MAX 1000000009
/*
對路徑長度和數量同時DP，
政策是對角線向起終點兩端擴充；
*/
int dp[N][N],n,pat[N][N];
int solve()
{
    int i,j,k,f;
    for(i=0;i<n;++i)
            pat[i][i]=1;
    for(k=1;k<n;++k)
        for(i=k,j=0;i<n;++i,++j)
            {
                f=dp[i][j+1]-dp[i-1][j];
                dp[i][j]+=dp[j][i];
                if(f>0)
                {
                    pat[i][j]=pat[i-1][j];
                    dp[i][j]+=dp[i-1][j];
                }
                else if(f<0)
                {
                    pat[i][j]=pat[i][j+1];
                    dp[i][j]+=dp[i][j+1];
                }
                else
                {
                    pat[i][j]=(pat[i][j+1]+pat[i-1][j])%MAX;
                    dp[i][j]+=dp[i][j+1];
                }
            }
    return pat[n-1][0];
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        int i,j;
        for(i=n-1;i>=0;--i)
            for(j=0;j<n;++j)
                scanf("%d",&dp[i][j]);
        printf("%d\n",solve());
    }
    return 0;
}