2014
02-24

# Ant on the graph

You are given a directed graph with n vertices, labeled 1 to n. The edges of the graph contain values, and each time you traverse an edge, the value of that edge you traverse was added to your total score. If the same edge is traversed multiple times, its value was added every time. Values can be any number between -499 and 499, inclusive. There are no edges that connect a vertex to itself.
There’s an ant at vertex 1 and it wants to get to vertex n. It must do this in an integer number of seconds between Tmin and Tmax, inclusive. The ant must make exactly one step each second, where each step consists of moving from its current vertex V to an adjacent vertex W (W is adjacent to V if there’s a directed edge from V to W in the graph). The ant’s goal is to get the highest score possible.

There are multiple test cases.
For each test case, the first line contains three integers, n, Tmin and Tmax (2<=n<=50, 1<=Tmin<=Tmax<=1000000000).
Following n lines, shows an n*n matrix. The element aij (-499<=aij<=499) which in the i-th row and j-th column indicates an edge from the vertex i to vertex j values aij. If the aij equals to -500, means such edge didn’t exist. The elements in the diagonal are always -500, which means aii=-500 all the time.

There are multiple test cases.
For each test case, the first line contains three integers, n, Tmin and Tmax (2<=n<=50, 1<=Tmin<=Tmax<=1000000000).
Following n lines, shows an n*n matrix. The element aij (-499<=aij<=499) which in the i-th row and j-th column indicates an edge from the vertex i to vertex j values aij. If the aij equals to -500, means such edge didn’t exist. The elements in the diagonal are always -500, which means aii=-500 all the time.

2 3 6
-500 1
1 -500

5
#include<iostream>
using namespace std;
//感谢 卡通blue和AC大神提供的测试数据非常orz
//注意对tmax=tmin时的考虑
//第一个矩阵计算用tmin步任意两点的最优值
//第二个针具计算前tmax-tmin步任意两点的最优值
const int maxn=50;
const __int64 INF=(__int64)1<<60;
typedef __int64 lld;
typedef struct node
{
lld v[maxn][maxn];
}node;
node d,e1,e2,e;
int n,tmin,tmax;
node mul1(node a,node b)
{
int i,j,k;
node c;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
c.v[i][j]=-INF;
for(k=0;k<n;k++)
{
if(a.v[i][k]==-INF||b.v[k][j]==-INF)continue;
c.v[i][j]=max(c.v[i][j],a.v[i][k]+b.v[k][j]);
}
}
return c;
}
node fen1(int k)
{
if(k==0)return e;
if(k==1)return d;
node p=d,t;
int c=0;
while(k)
{
if(k&1)
{
if(c==0)t=p;
else t=mul1(t,p);
c++;
}
p=mul1(p,p);
k>>=1;
}
return t;
}

node mul2(node a,node b)
{
int i,j,k;
node c=a;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
if(a.v[i][k]==-INF||b.v[k][j]==-INF)continue;
c.v[i][j]=max(c.v[i][j],a.v[i][k]+b.v[k][j]);
}
}
return c;
}
node fen2(int k)
{
if(k==0)return e;
if(k==1)return d;
node p=d,t;
int c=0;
while(k)
{
if(k&1)
{
if(c==0)t=p;
else t=mul2(t,p);
c++;
}
p=mul2(p,p);
k>>=1;
}
return t;
}
int main()
{
int i,j,k;
for(i=0;i<50;i++)for(j=0;j<50;j++)e.v[i][j]=0;
for(i=0;i<50;i++)e.v[i][i]=1;
while(scanf("%d%d%d",&n,&tmin,&tmax)!=EOF)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%I64d",&d.v[i][j]);
if(d.v[i][j]==-500)d.v[i][j]=-INF;
}
/*          for(i=1;i<=5;i++)
{
e1=fen1(i);
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
if(e1.v[j][k]==-INF)printf("INF ");
else printf("%I64d ",e1.v[j][k]);
}
printf("\n");
}
system("pause");
}*/

e1=fen1(tmin);
d.v[n-1][n-1]=0;
e2=fen2(tmax-tmin);
lld ans=-INF;
if(tmax==tmin)ans=e1.v[0][n-1];
else
{
for(k=0;k<n;k++)if(e1.v[0][k]!=-INF&&e2.v[k][n-1]!=-INF)ans=max(ans,e1.v[0][k]+e2.v[k][n-1]);
}
if(ans==-INF)printf("IMPOSSIBLE\n");
else cout<<ans<<endl;
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。