UVA - 12295 最短路（迪杰斯特拉）——求按对称路线最短路条数

题意：

给你一个n，然后给你一个n*n的正方形w[i][j]，你需要找到一个从(1,1)点走到(n,n)点的最短路径数量。而且这个路径必须按照y=x对称

题解：

我们把左上角的点当作(0,0)点，右下角的点当作(n,n)点

因为路径必须按照y=x堆成，那么我们可以按照y=x这一条线对折，然后正方形就变成了三角形，我们把对折成三角形后两点在同一位置的值相加，比如(1,1)和（n，n）对折后在一个位置，那么我们就让w[1][1]+=w[n][n]（这里我们保留左上部分）。

然后你按照左上部分从(0,0)点只要走到对称线y=x的点上，这就是一个从左上角到右下角的一条路径（可以想一想）

那么我们就可以对这个上半部分的三角形就行bfs式的最短路遍历

代码：

fill函数的作用是：将一个区间的元素都赋予val值。函数参数：fill(vec.begin(), vec.end(), val); val为将要替换的值。

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <cctype>

  4 #include<queue>

  5 #include<vector>

  6 #include <algorithm>

  7 using namespace std;

  8 const int maxn=105;

  9 const int INF=1e9+10;

 10 const int mod=1e9+9;

 11 typedef long long LL;

 12 int n,dp[maxn][maxn],w[maxn][maxn],counts[maxn][maxn];

 13 //dp[x][y]求的是从（0，0）点到（x，y）点的最短路径值（也就是最短路）

 14 //counts[x][y]求的是从（0，0）点到（x，y）点的最短路径数量

 15 int p[4][2]=

 16 {

 17     {1,0},

 18     {0,1},

 19     {-1,0},

 20     {0,-1}

 21 };

 22 struct shudui

 23 {

 24     int x,y,lx,ly,dis;

 25     shudui() {}

 26     shudui(int x,int y,int lx,int ly,int dis)

 27     {

 28         this->x=x;

 29         this->y=y;

 30         this->lx=lx;

 31         this->ly=ly;

 32         this->dis=dis;

 33     }

 34     bool operator < (const shudui a)const

 35     {

 36         return a.dis<dis;

 37     }

 38 } str1;

 39 priority_queue<shudui>r;

 40 void JK()

 41 {

 42     for(int i=0; i<maxn; ++i)

 43         fill(dp[i],dp[i]+maxn,mod);

 44     counts[0][0]=1;

 45     r.push(shudui(0,0,0,0,w[0][0]));

 46     while(!r.empty())

 47     {

 48         str1=r.top();

 49         r.pop();

 50         int x=str1.x;

 51         int y=str1.y;

 52         int lx=str1.lx;

 53         int ly=str1.ly;

 54         int dis=str1.dis;

 55         if(dp[x][y]>dis)

 56         {

 57             dp[x][y]=dis;

 58             counts[x][y]=counts[lx][ly];

 59         }

 60         else if(dp[x][y]==dis)

 61         {

 62             counts[x][y]=(counts[x][y]+counts[lx][ly])%mod;

 63             continue;

 64         }

 65         else continue;

 66

 67         if(x+y>=n-1) continue;

 68         for(int i=0; i<4; ++i)

 69         {

 70             int xx=x+p[i][0];

 71             int yy=y+p[i][1];

 72             if(xx<n && yy<n && xx>=0 && yy>=0)

 73             {

 74                 r.push(shudui(xx,yy,x,y,dis+w[xx][yy]));

 75             }

 76         }

 77     }

 78 }

 79 int main()

 80 {

 81     while(~scanf("%d",&n) && n)

 82     {

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

 84         {

 85             for(int j=0; j<n; ++j)

 86             {

 87                 scanf("%d",&w[i][j]);

 88             }

 89         }

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

 91         {

 92             for(int j = 0; j < n-i-1; j++)

 93             {

 94                 w[i][j] += w[n-j-1][n-i-1];

 95             }

 96         }

 97         JK();

 98         int minn=mod;

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

100         {

101             minn=min(minn,dp[i][n-i-1]);

102         }

103         int ans=0;

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

105         {

106             if(dp[i][n-i-1]==minn)

107             {

108                 ans=(ans+counts[i][n-i-1])%mod;

109             }

110         }

111         printf("%d\n",ans);

112     }

113     return 0;

114 }

巴特西

UVA - 12295 最短路（迪杰斯特拉）——求按对称路线最短路条数

最新文章

热门文章