250 条题解
-
10
PowderHan LV 10 @ 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)); }-
moshtian @ 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; } -
Elucidator @ 2018-07-21 09:11:12
@moshtian: 数据水喽。。。
-
-
4
qq913653500 LV 10 @ 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
Sky1231 (sky1231) LV 10 @ 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(); } -
0
#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;
} -
0
#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;
} -
0
#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;
} -
0
乱打了一个
#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; * } -
0
#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];
} -
0
艹了个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;
} -
0
feng_lingsong LV 9 @ 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;
}-
lambdacat @ 2016-12-16 09:12:25
最短路，很猥琐的样子
-
-
0
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;
} -
0
#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");
} -
0
#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
测试数据 #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
#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
williamking5 LV 8 @ 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
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.
总算看着题解过了…… -
0
测试数据 #0: Accepted, time = 46 ms, mem = 14152 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 14156 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 14156 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 14152 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 14152 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 14156 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 14152 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 14156 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 14152 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 14152 KiB, score = 10 -
0
邻接矩阵+SPFA，预处理麻烦一点，额呵呵、、本人是渣，目前没有优化==时效也很低==看到楼上各种大神的方法表示汗颜==
PROGRAM 1006;
var q,d,A:array[1..500500] of longint;
v:array[1..500500] oF Boolean;
co,sT:array[1..500500,0..6] of longint;
N,m,x,i,j,b,c,k,h,T:longint;bEgin
{assign(input,'1006.in');
reset(input);
assign(output,'1006.out');
rewrite(output);}readln(n);
read(a[1]); read(a[2]); read(a[3]); k:=3;
cO[2,0]:=2; co[2,1]:=1; st[2,1]:=a[1]; co[2,2]:=3; st[2,2]:=a[3];
co[3,0]:=2; co[3,1]:=1; st[3,1]:=a[1]; co[3,2]:=2; st[3,2]:=a[2];
for i:=3 to n do
for j:=1 to i do
begin
inc(k); read(a[K]);
if j=1 then begin
inc(co[k,0]); co[k,co[k,0]]:=k-i+1; st[k,co[k,0]]:=a[k-i+1];
inc(co[k,0]); co[k,co[k,0]]:=k-1; st[k,co[k,0]]:=a[k-1];
end Else if j=i then begin
inc(co[k,0]); co[k,co[k,0]]:=k-i; st[k,co[k,0]]:=a[k-i];
inc(co[k,0]); co[k,co[k,0]]:=k-i-i+2; st[k,co[k,0]]:=a[k-i-i+2];
inc(co[k,0]); co[k,co[k,0]]:=k-1; st[k,co[k,0]]:=a[k-1];
inc(co[k-1,0]); co[k-1,co[k-1,0]]:=k; st[k-1,co[k-1,0]]:=a[k];
inc(co[k,0]); co[k,co[k,0]]:=k-i+1; st[k,co[k,0]]:=a[k-i+1];
inc(co[k-I+1,0]); co[k-i+1,co[k-i+1,0]]:=k; st[k-i+1,co[k-i+1,0]]:=a[k];
end else begin
inc(co[k,0]); co[k,co[k,0]]:=k-i+1; st[k,co[k,0]]:=a[k-i+1];
inc(co[K,0]); co[k,co[k,0]]:=k-i; st[k,co[k,0]]:=a[k-i];
inc(co[k,0]); co[k,co[k,0]]:=k-1; st[k,co[k,0]]:=a[k-1];
inc(co[k-1,0]); co[k-1,co[k-1,0]]:=k; st[k-1,co[k-1,0]]:=a[k];
end;
end;
for i:=1 to k do D[i]:=maXlongint;
inc(t); q[t]:=k-n+1; d[k-n+1]:=a[k-n+1]; v[k-n+1]:=true;
While h<>t do
begin
H:=h mod k+1;
x:=q[h];
v[x]:=false;
for i:=1 to co[x,0] do
if d[x]+st[x,i]<d[co[x,i]] then begin
d[co[x,i]]:=d[x]+st[x,i];
if not V[co[x,i]] then begin
v[co[x,i]]:=true;
t:=t mod k+1;
q[t]:=co[x,i];
end;
enD;
end;
writeln(d[1]);{close(input);
cloSe(output);}
eNd.
PowderHan
LV 10
@ 2017-05-07 12:42:53
