题目很简单,就是求一个带点权最大的最短路,lrj说的很清楚可以用Dijkstra加枚举点处理;在UVA的讨论上看到在问Floyd-Warshall的算法如何用在这道题目上!应该是可以的,只是就像lrj说的一样,多次查询打表是比较好的策略。其他没有什么,只是敲代码的时候,忘记了f(tmp!=INT_MAX&&tmp+pcost[j]<pcost[k]) pcost[k]=tmp+pcost[j]; 开始写成tmp了,眼花看了半天,结果还从头到尾把算法过了一遍!这个毛病和原来奥数比赛时候一样,晃得一脉相承,要注意了,敲代码要精神集中!有个很明显的改进,lrj说要把比X贵的城市删除,这里直接用qsort排序,然后反向求其范围,不算改进吧,常识的处理。

另外就是一点感概,UVA确实比PKU要严谨,多一个换行都是WA,要提醒自己多注意细节的问题!细节决定成败!

My Submissions

#

Problem

Verdict

Language

Run Time

Submission Date

7082960 10246  Asterix and Obelix 

Accepted

C++

0.430

2009-04-21 03:33:21
7082927 10246 Asterix and Obelix 

Wrong answer

C++

0.450

2009-04-21 02:47:30

代码如下:

#include <iostream>
#include <fstream>

//UVA 10246 – Asterix and Obelix
using namespace std;
const int MAXC=81, MAXR=1001;//MAX Edges
typedef struct Edge{
    int i, j, cost, next1, next2;//for link to other i->next edges
};
typedef struct City{
    int n, cost;
};
Edge es[MAXR];
int first[MAXC],LC[MAXC][MAXC], city[MAXC], pcost[MAXC], eid=0, c, r, q;//or 0xff should be the maxmimal
City CC[MAXC];
bool inG[MAXC], inD[MAXC];

//declaration
void addEdge(int s, int e, int cost);
int cmp(const void* p1, const void* p2);
int getCost(int x, int y);
void DijsktraEach(int i);
void Dijkstra(int v);//v is the starting city, to all cities inG[1…n] is true;

//implementation
void DijsktraEach(int i){//first of all, earse all cities
    memset((void*)inG, 0, sizeof(inG));
    for(int k=i; k<=c; k++) inG[CC[k].n]=true;//make in city
    int x=CC[i].n; LC[x][x]=CC[i].cost;//sit for city x’s self
    if(i!=c) Dijkstra(x);//order correctly
}
void Dijkstra(int v){
    //the last value is for +LC[x][x]
    int vn=0;
    for(int i=1; i<=c; i++){
        if(!inG[i]){inD[i]=true; continue;}
        inD[i]=false; pcost[i]=INT_MAX; vn++;
    }
    for(int x=first[v]; x!=-1; ){//find the next slot
        int t1=es[x].i, t2=es[x].j;
        //next logic
        if(t1==v) pcost[t2]=es[x].cost, x=es[x].next1;
        else if(t2==v) pcost[t1]=es[x].cost, x=es[x].next2;//just neighbour could add LC[v][v], error
    }
    inD[v]=true;//OK, let’s for dijstra
    int tmp=INT_MAX, j=v;
    for(int i=1; i<vn; i++){
        tmp=INT_MAX;
        for(int k=1; k<=c; k++){
            if(!inD[k]&&pcost[k]<tmp) tmp=pcost[k], j=k;
        }
        if(inD[j]) continue;//if j==v, avoid exception
        inD[j]=true; LC[v][j]=LC[j][v]=pcost[j]+LC[v][v];
        //update the other points in the sets
        for(int k=1; k<=c; k++){
            if(!inD[k]){
                int tmp=getCost(k, j);
                if(tmp!=INT_MAX&&tmp+pcost[j]<pcost[k]) pcost[k]=tmp+pcost[j];//mimnal
            }
        }
    }
}
int getCost(int x, int y){
    int cost=INT_MAX;
    for(int x1=first[x]; x1!=-1; ){
        int t1=es[x1].i, t2=es[x1].j;
        if(t1==x){
            if(y==t2) cost=es[x1].cost;
            x1=es[x1].next1;
        }
        else if(t2==x){
            if(y==t1) cost=es[x1].cost;
            x1=es[x1].next2;
        }
    }
    return cost;
}
void addEdge(int s, int e, int cost){
    es[eid].i=s, es[eid].j=e, es[eid].cost=cost;
    es[eid].next1=first[s], first[s]=eid;//bi-direction!yeah, don’t forget
    es[eid].next2=first[e], first[e]=eid;//next1 for i, next2 for j.
    eid++;
}
int cmp(const void* p1, const void* p2){//deceasing order, remember the order
    return ((City*)p1)->cost<((City*)p2)->cost;
}

#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif

    //implementation
    int s, e, cost, c1, c2, id=1;
    cin>>c,cin>>r,cin>>q;
    do{
        if(c==0&&r==0&&q==0) break;//quit the game
        eid=0;memset((void*)first, 0xff, sizeof(first));
        for(int i=1; i<=c; i++) for(int j=1; j<=c; j++) LC[i][j]=INT_MAX;//intial index
        for(int i=1; i<=c; i++) cin>>CC[i].cost, CC[i].n=i;//cost for each city
        for(int i=1; i<=r; i++){
            cin>>s, cin>>e, cin>>cost;
            addEdge(s, e, cost);//set for first and next value
        }
        //qsort for city
        qsort((void*)(CC+1), c, sizeof(City), cmp);
        for(int i=1; i<=c; i++){//from CC[i].n->CC[i].cost decending order, to generate DP table
            DijsktraEach(i);
        }
        cout<<"Case #"<<(id++)<<endl;
        for(int i=1; i<=q; i++){
            cin>>c1, cin>>c2;
            int lcost=INT_MAX;
            for(int j=1; j<=c; j++){
                if(LC[c1][j]==INT_MAX||LC[c2][j]==INT_MAX) continue;
                int tmp=LC[c1][j]+LC[c2][j]-LC[j][j];
                if(tmp<lcost) lcost=tmp;
            }
            if(lcost==INT_MAX) cout<<-1<<endl;
            else cout<<lcost<<endl;
        }
        cin>>c,cin>>r,cin>>q;
        if(c!=0||r!=0||q!=0) cout<<endl;
    }while(c!=0||r!=0||q!=0);

#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase

  • 最短路算法的总结和应用
两个类型:一种是标号修正法,思想和Dinkench算法一样,不断逼近最终达到其上下限;第二种是标号设定算法,对临时标号不断修改,然后不能修改的最优就是固定标号!
PS:开始小瞧了这个思想,结果搞得自己头晕眼花的,其实标号设定算法也可以看作是一种拓扑序的计算过程;只是这是的拓扑序不像一般的图一样是基于边的变换,而是基于最终值的一个序列,想通了这点下面的题目就简单了;没想通就有苦头吃了!
 
1,Crossing the desert,这是一道ACM/ICPC的world fina 2002l的题目,和楼教主他们做的题目不一样,这个题估计要被教主在15分钟之内秒杀哟!
两点容易错:题目给的是int,但实际上要用double来做,读题不细心,卡了好久;还有就是这里所有临时标号都是基于当前最优标号值得,这和dijkstra的思路有些不同,生搬硬套,吃了苦头!顺便练习了下循环队列的写法,在没有carlo提示之前,我一直以为是自己算法有问题,换了好几种算法,不是WA就是TLE,哭死了,结果是精度问题!下面是AC的代码:
 
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5. const int MAXN=31, MAXS=1000004;
  6. struct Oase{
  7.     double x,y;
  8. };
  9. double dis[MAXN][MAXN], d[MAXN], cap;
  10. int n;
  11. Oase os[MAXN];
  12. bool inG[MAXN];
  13.  
  14. int main()
  15. {
  16.     //implementation
  17.     double tmp, m;
  18.     int k, sum, id=1;
  19.     while(cin>>n&&cin>>cap&&n&&cap){
  20.         for(int i=1; i<=n; i++) cin>>os[i].x, cin>>os[i].y, inG[i]=false, d[i]=MAXS;
  21.         for(int i=1; i<=n; i++)
  22.             for(int j=i+1; j<=n; j++)
  23.                 dis[i][j]=dis[j][i]=sqrt((os[i].x-os[j].x)*(os[i].x-os[j].x)+(os[i].y-os[j].y)*(os[i].y-os[j].y));
  24.         d[n]=0; inG[n]=true;
  25.         for(int i=1; i<n; i++){
  26.             m=2*dis[n][i]-cap;
  27.             if(m>0&&cap-3*dis[n][i]>0){
  28.                 tmp=(ceil(m/(cap-3*dis[n][i]))*2+1)*dis[n][i];
  29.                 if(tmp<d[i]) d[i]=tmp;
  30.             }
  31.             else if(cap-2*dis[n][i]>=0){
  32.                 tmp=dis[n][i];
  33.                 if(tmp<d[i]) d[i]=tmp;
  34.             }
  35.         }
  36.         //dijkstra
  37.         for(int i=1; i<n; i++){
  38. tmp=MAXS, k=-1;
  39.             for(int i=1; i<n; i++){
  40.                 if(!inG[i]&&d[i]<tmp) tmp=d[i], k=i;
  41.             }
  42.             if(k==-1) break;
  43.             inG[k]=true;
  44.             for(int i=1; i<n; i++){
  45.                 if(!inG[i]){
  46.                     m=d[k]-cap+2*dis[i][k];
  47.                     if(m>0&&cap-3*dis[i][k]>0){
  48.                         tmp=(ceil(m/(cap-3*dis[i][k]))*2+1)*dis[i][k]+d[k];
  49.                         if(tmp<d[i]) d[i]=tmp;
  50.                     }
  51.                     else if(cap-2*dis[i][k]-d[k]>=0){
  52.                         tmp=dis[i][k]+d[k];
  53.                         if(tmp<d[i]) d[i]=tmp;
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.         sum=(int)ceil(d[1]);
  59.         if(sum==0) sum++;
  60.         if(sum>1000000)
  61.             cout<<"Trial "<<(id++)<<": Impossible "<<endl<<endl;
  62.         else
  63.             cout<<"Trial "<<(id++)<<": "<<sum<<" units of food"<<endl<<endl;
  64.     }
  65.     return 0;
  66. }
2.UVA 10381 The Rock,这道题目让我异常痛苦,换了三种算法,两个TLE,一个后面有个严重的漏洞!现在都还没有过,最好的跑了5s多,最差的跑了18s。还是说下思路吧,以后有好的思路再来弄它!
算法分析:最坏的最短时间设为d[i], i=1…x*y,问题在于当前的一个石头是不可知的;由于d[i]的序列是严格增加的,在出口处为d[exit]=0,反向到入口求出d[extrance],那么结果就可以知道了。下面有点像动规,对于当前要求得点i,如果它在d[i]求解序列的拓扑上一个点的d是可知的,那么一定有以下两种情况:
  • 若上一个拓扑序的点为石头,那么可以求一条新的最短路到exit,这个时候值为distance[i, A],i为石头,A为当前点,表示i为石头的时A到出口的最短路长;
  • 若为空白,加个1,即可。

至于如果求出d的严格增加序列,一个最小堆处理即可。下面是实现代码,算法瓶颈在于distance[i, A],求得痛苦无比,开始放在预处理里面,跑料18s;然后用DP打表,就是现在的版本了,还是很慢!

#include <iostream>
#include <fstream>

using namespace std;
//UVA 10381 – The Rock
const int MAXN=1600, MAXD=4;
char map[MAXN];//0 for space, 1 for wall;
int r, c, exits, b, extrance, size, dis[MAXN][MAXN],/*pre-calculation*/
    d[MAXN], cost[MAXN], queue[MAXN];
int dx[4]={0,0,-1,1}, dy[4]={-1,1,0,0};//left 0, right 1, up 2, down 3
bool inG[MAXN], inQ[MAXN];

//declaration
int Dijkstra(int stone);//set stone position as wall, then use dijkstra to calculate shortest path.
void backtrack();//set d[exit]=0, backtrack to d[extrance].
//heap implemenation
void pushHeap(int cur);
int popHeap();
int cmp(const int& p1, const int& p2);

void inline pushHeap(int cur){
    if(size==MAXN) return;
    queue[size++]=cur;
    if(size>1) push_heap(queue, queue+size, cmp);
}
int inline popHeap(){
    if(size==0) return -1;
    if(size>1) pop_heap(queue, queue+size, cmp);
    size–; return size;
}
int cmp(const int& p1, const int& p2){
    return d[p1]>d[p2];
}

//implementation
int Dijkstra(int stone, int v){
    if(dis[stone][v]!=-1) return dis[stone][v];
    map[stone]=1;
    //from exit point backtrack to all reachable points
    for(int i=0; i<b; i++){
        cost[i]=INT_MAX;
        if(map[i]==1) inG[i]=true;//for stone check
        else inG[i]=false;
    }
    inG[exits]=true, cost[exits]=0, dis[stone][exits]=0;
    //set 4 direction for exit
    int x=exits/c, y=exits%c;
    for(int i=0; i<4; i++){
        if(x+dx[i]>-1&&x+dx[i]<r&&y+dy[i]>-1&&y+dy[i]<c){//no stone
            int p=(x+dx[i])*c+y+dy[i];
            if(!inG[p]) cost[p]=1;//take care of
        }
    }
    //Dijstra algorithm
    int tmp, k;
    for(int i=1; i<b; i++){//for add i’s vertexs
        //find the mimal amount
        tmp=INT_MAX, k=-1;
        for(int j=0; j<b; j++){//?can we optimize it
            if(!inG[j]&&cost[j]<tmp) tmp=cost[j], k=j;
        }
        if(k==-1) break;
        inG[k]=true, dis[stone][k]=cost[k];
        if(k==v) {map[stone]=0; return dis[stone][v];}
        x=k/c, y=k%c;
        for(int j=0; j<4; j++){//O(1)
            if(x+dx[j]>-1&&x+dx[j]<r&&y+dy[j]>-1&&y+dy[j]<c){
                int p=(x+dx[j])*c+(y+dy[j]);
                if(!inG[p]&&cost[k]+1<cost[p]) cost[p]=cost[k]+1;
            }
        }
    }
    map[stone]=0; return dis[stone][v];
}
void backtrack(){
    memset((void*)inQ, 0, sizeof(bool)*b);
    size=0; pushHeap(exits), inQ[exits]=true, d[exits]=0;
    while(size){
        int cur=queue[popHeap()];
        //update 4’s direction for grid
        int x=cur/c, y=cur%c, p, tmp;
        for(int i=0; i<4; i++){//cur is adjacent to p
            if(x+dx[i]>-1&&x+dx[i]<r&&y+dy[i]>-1&&y+dy[i]<c){
                p=(x+dx[i])*c+(y+dy[i]);
                if(!inQ[p]&&map[p]==0){//possible
                    tmp=d[cur]+1;
                    int t1=(dis[cur][p]==-1?Dijkstra(cur, p):dis[cur][p]);
                    if(cur!=exits&&cur!=extrance&&t1!=-1
                        &&dis[cur][p]>tmp) tmp=t1;
                    if(tmp>d[p]&&d[p]==-1) d[p]=tmp;
                    //using priority_queue instead of circlar queue.
                    if(p==extrance) return;
                    pushHeap(p), inQ[p]=true;
                }
            }
        }
    }
}

#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif

    //implementation
    char ch; int ncase;
    cin>>ncase;
    while(ncase–){
        cin>>r, cin>>c;
        b=r*c;
        for(int i=0; i<b; i++){
            cin>>ch;
            if(ch==’.’) map[i]=0;
            else if(ch==’#’) map[i]=1;
            else if(ch==’E’) map[i]=0, extrance=i;
            else if(ch==’X’) map[i]=0, exits=i;
        }
        memset((void*)dis, 0xff, sizeof(dis)),
        memset((void*)d, 0xff, sizeof(d));//clr
        backtrack();
        cout<<d[extrance]<<endl;
    }

#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase

  • 第二个思路是,不管三七二十一先求出最短路,注意这里的特殊情况,第一是一个正方形网格,那么从一点到另一点无重叠的最短路最多两条,题目上说是只有一条那么就简单多了。一点没有相通的问题:我们如何求出在最短路上有石头时,新的最短路上最坏最短时间呢?比如我可以求出初始最短路的最坏最短时间为17,OK,那么用了一条新的路,这条路路长为13,但假设石头在其上的时候,路长肯定要变大;这个解法是基于路的,换句话说就不是一个严格的d拓扑序列,不能保证在反向达到入口时求出的d值一定是最优,但要求出最优,也就是要枚举每个可能道路,直接疯掉!下面是写了一半卡做的代码[希望以后有时间能补上这个遗憾,或者向高手请教一下!]

#include <vector>
#include <iostream>
#include <fstream>

using namespace std;
//UVA 10381 – The Rock
const int MAXN=1600, MAXD=4;
char map[MAXN];//0 for space, 1 for wall;
int r, c, exits, b, extrance, size,
    sig, d[MAXN], cost[MAXN], buf[MAXN];
int dx[4]={0,0,-1,1}, dy[4]={-1,1,0,0};//left 0, right 1, up 2, down 3
bool inG[MAXN], inQ[MAXN];
vector<int> spath;

//declaration
int Dijkstra(int v, bool s);//set stone position as wall, then use dijkstra to calculate shortest path.
void backtrack();//set d[exit]=0, backtrack to d[extrance].
void tracepath(int v, int step);

//implementation
int Dijkstra(int v, bool s){
    //from exit point backtrack to all reachable points
    for(int i=0; i<b; i++){
        buf[i]=INT_MAX;
        if(map[i]==1) inG[i]=true;//for stone check
        else inG[i]=false;
    }
    inG[v]=true, buf[v]=0;
    //set 4 direction for exit
    int x=v/c, y=v%c;
    for(int i=0; i<4; i++){
        if(x+dx[i]>-1&&x+dx[i]<r&&y+dy[i]>-1&&y+dy[i]<c){//no stone
            int p=(x+dx[i])*c+y+dy[i];
            if(!inG[p]) buf[p]=1;//take care of
        }
    }
    //Dijstra algorithm
    int tmp, k;
    for(int i=1; i<b; i++){//for add i’s vertexs
        //find the mimal amount
        tmp=INT_MAX, k=-1;
        for(int j=0; j<b; j++){//?can we optimize it
            if(!inG[j]&&buf[j]<tmp) tmp=buf[j], k=j;
        }
        if(k==-1) break;
        inG[k]=true;
        if(s){
            if(k==exits) return buf[k];
        }
        x=k/c, y=k%c;
        for(int j=0; j<4; j++){//O(1)
            if(x+dx[j]>-1&&x+dx[j]<r&&y+dy[j]>-1&&y+dy[j]<c){
                int p=(x+dx[j])*c+(y+dy[j]);
                if(!inG[p]&&buf[k]+1<buf[p]) buf[p]=buf[k]+1;
            }
        }
    }
    if(!s) memcpy((void*)cost, (void*)buf, sizeof(int)*b);
    return -1;
}
void tracepath(int v, int step){
    if(sig) return;
    if(v==extrance){//buf as queue, d as direction
        for(int i=0; i<step; i++) spath.push_back(buf[i]);
        spath.push_back(extrance);
        sig=1; return;
    }
    int x=v/c, y=v%c; buf[step]=v, inG[v]=true;
    for(int i=0; i<4; i++){
        if(x+dx[i]>-1&&x+dx[i]<r&&y+dy[i]>-1&&y+dy[i]<c){
            int p=(x+dx[i])*c+(y+dy[i]);
            if(!inG[p]&&cost[p]==cost[v]+1){//not in the dfs and forward step
                tracepath(p, step+1);
            }
        }
    }
}

#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif

    //implementation
    char ch; int ncase, total;
    cin>>ncase;
    while(ncase–){
        cin>>r, cin>>c;
        b=r*c;
        for(int i=0; i<b; i++){
            cin>>ch;
            if(ch==’.’) map[i]=0;
            else if(ch==’#’) map[i]=1;
            else if(ch==’E’) map[i]=0, extrance=i;
            else if(ch==’X’) map[i]=0, exits=i;
        }
        memset((void*)d, 0xff, sizeof(d));//clr
        Dijkstra(exits, false), spath.clear();
        memset((void*)inG, 0, sizeof(bool)*b);//trace the shortest path
        sig=0, tracepath(exits, 0);
        d[exits]=0;
        int len=spath.size(), min=INT_MIN;
        for(int i=1; i<len; i++){//spath[i], d[spath[i-1].i]+1 and spath[i].i->exits
            int tmp=d[spath[i-1]]+1;
            if(i!=1){
                map[spath[i-1]]=1;
                int t1=Dijkstra(spath[i], true);
                //cout<<spath[i]<<" "<<t1;
                map[spath[i-1]]=0;
                if(t1>tmp) tmp=t1;
            }
            d[spath[i]]=tmp;
            //cout<<" "<<tmp<<endl;
        }
        cout<<d[extrance]<<endl;
    }

#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase

 

3. 最优双调路径,虽然这道最后,但个人觉得这道题目的思路很重要,让我想起来了处理二维最大和的算法(当然,那个还有一个预处理的技巧),一个模型不能处理的时候,可以考虑固定其一个参数,然后用通用模型来处理固定参数之后的模型!如果没有第二个路权参数,那么这就完全是个很菜的最优路,现在多了一个参数,那么我们就枚举这个路权即可。[怎么办呢?我参照了下标程,主要一个是被上面的题搞得晕头转向的,加上lrj说的不清不楚的,这下彻底菜了!一看代码,呵呵,原来是一个枚举加滚动数组,OK]

注意:

1。滚动数组的大小4*101即可,边长为101的上限,呵呵,很省空间!
2。jim哥哥的代码看得我好想吐哟,一m多的vector,最让我不爽的是这个time(n,k)表示n城市k费用到s时的最短时间!其实在c++里面有一种叫代理类的方式,可以帮助我们将time(n,k)转化为time[n][k],可惜!我比较菜,没有想到很好的传参的方式,写的严重破坏OO,没有看到Scott的实现怎么样的!
3。最后在写Dijkstra的时候,才发现lrj说的标号固定是个什么意思;我们先用0-1背包的思想生成k+1的最短旅行时间,由于0权费用路的存在,那么就用反复修正,输出不可变的固定标号!好的程序员说话就像在飘,太飘了,看来只有用代码说话了!NKU上直接切掉!
Solution User Problem Language Judge Result Memory Time Used Code Length Submit Time
261471 orlando22 10702 GNU C++ Accepted 1336KB 3343ms 5080B 2009-04-25 16:21:45.0
Source Code
#include <iostream>
#include <algorithm>

using namespace std;
const int INF=1000000000, MAXT=100, MAXE=300, MAXC=101;
struct Edge{
    int i, j, c, t, next1, next2;
};

int n, m, s, e, dist[MAXC], heap[MAXC];
bool inHeap[MAXC];

//forward-start for zero and non-zero t links
//declaration for edge implemenation
int eid=0, zeroC[MAXC], nzeroC[MAXC];
Edge es[MAXE];
void inline clrE();
void inline addEdge(int i, int j, int c, int t);

//implemenation
void inline clrE(){
    memset((void*)zeroC, 0xff, sizeof(zeroC)),
    memset((void*)nzeroC, 0xff, sizeof(nzeroC));
}
void inline addEdge(int i, int j, int c, int t){
    es[eid].i=i, es[eid].j=j, es[eid].c=c, es[eid].t=t;
    if(c==0){//insert into zeroC
        es[eid].next1=zeroC[i], zeroC[i]=eid;
        es[eid].next2=zeroC[j], zeroC[j]=eid;
    }
    else{
        es[eid].next1=nzeroC[i], nzeroC[i]=eid;
        es[eid].next2=nzeroC[j], nzeroC[j]=eid;
    }
    eid++;
}

//declaration for scroll array
class Scroll{
private:
    int *p, sn, stoll;
    friend class Scroll2D;//access by inner class
    class Scroll2D{
        friend class Scroll;//access by outer class
        private:
            int dim1; Scroll *ip;
        public:
            Scroll2D(Scroll* _p):ip(_p){}
            int& operator[](int dim2){//jim哥哥很强的代码,滚动数组的逻辑!
                return ip->p[dim1+((dim2+ip->stoll)%ip->stoll)*ip->sn];//2->1;
            }
    }proxy;
public:
    Scroll(int n, int toll) : sn(n), stoll(toll), proxy(this){
        p=new int[sn*stoll];
    }
    ~Scroll(){
        delete[] p;
    }
    void init(){
        for(int i=0; i<sn*stoll; i++) p[i]=INF;
    }
    Scroll2D operator[](int dim1){
        proxy.dim1=dim1;//让我极其不爽的一行代码,哪位高手给指点下,正规做法是什么,Scott的代码看不到!
        return proxy;
    }
};

//Dijkstra algorithm
void Dijkstra(Scroll& time, int toll);
void ReviseForCurrent(Scroll& time, int toll);
//heap declaration
void inline pushHeap(int v, int& size);
int inline popHeap(int& size);
int cmp(const int& p1, const int& p2);
//heap implemenation 把heap的实现用STL的方法简单做了下!
void inline pushHeap(int v, int& size){
    heap[size]=v, inHeap[v]=true, size++;
    if(size>1) push_heap(heap, heap+size, cmp);
}
int inline popHeap(int& size){
    if(size>1) pop_heap(heap, heap+size, cmp);
    size--; inHeap[heap[size]]=false; return heap[size];
}
int cmp(const int& p1, const int& p2){
    return dist[p1]>dist[p2];
}

//impelementation
void Dijkstra(Scroll& time, int toll){
    for(int i=0; i<n; i++) heap[i]=i, dist[i]=time[i][toll], inHeap[i]=true;
    int size=n, cur;
    make_heap(heap, heap+size, cmp);
    while(size){
        cur=popHeap(size);//minmal one travelling time can't be changed any more, so...
        for(int i=zeroC[cur]; i!=-1; ){
            if(es[i].i==cur){//.i->.j
                if(dist[es[i].j]>dist[es[i].i]+es[i].t){//bugs here,开始这里用min做的,直接死循环了,吐血!
                    dist[es[i].j]=dist[es[i].i]+es[i].t;
                    make_heap(heap, heap+size, cmp);//注意堆修改后的调整,不然要报invalid heap
                    if(!inHeap[es[i].j]) pushHeap(es[i].j, size);
                }
                i=es[i].next1;
            }
            else if(es[i].j==cur){//.j->.i
                if(dist[es[i].i]>dist[es[i].j]+es[i].t){
                    dist[es[i].i]=dist[es[i].j]+es[i].t;
                    make_heap(heap, heap+size, cmp);
                    if(!inHeap[es[i].i]) pushHeap(es[i].i, size);
                }
                i=es[i].next2;
            }
        }
    }//revise dist, until non-dist array items can't be changed any more!
    for(int i=0; i<n; i++) time[i][toll]=dist[i];
}

void ReviseForCurrent(Scroll& time, int toll){//revise based on previous value
    for(int i=0; i<n; i++){
        for(int k=nzeroC[i]; k!=-1; ){
            if(es[k].i==i){//single out i->j
                if(time[es[k].j][toll]>time[es[k].i][toll-es[k].c]+es[k].t)
                    time[es[k].j][toll]=time[es[k].i][toll-es[k].c]+es[k].t;
                else time[es[k].j][toll]=time[es[k].j][toll];//modify set current!
                k=es[k].next1;
            }
            else if(es[k].j==i){//single out j->j;
                if(time[es[k].i][toll]>time[es[k].j][toll-es[k].c]+es[k].t)
                    time[es[k].i][toll]=time[es[k].j][toll-es[k].c]+es[k].t;
                else time[es[k].i][toll]= time[es[k].i][toll];
                k=es[k].next2;
            }
        }
    }
}

int main()
{
    //implementation
    int s1, t1, c, t, roads=0, minT;
    clrE();
    cin>>n>>m>>s>>e; s--,e--;
    for(int i=0; i<m; i++){
        cin>>s1>>t1>>c>>t;
        addEdge(s1-1, t1-1, c, t);
    }
    Scroll time(n, MAXT+1);
    time.init();//set [0...n-1][k=0]=INF
    time[s][0]=0;
    Dijkstra(time, 0);
    minT=time[e][0];
    if(minT<INF) roads++;
    for(int toll=1; toll<=n*MAXT; toll++){
        for(int i=0; i<n; i++) time[i][toll]=INF;
        ReviseForCurrent(time, toll);//revise toll based on previous toll,0-1背包处理
        Dijkstra(time, toll);
        if(time[e][toll]<minT) minT=time[e][toll], roads++;
    }
    cout<<roads<<endl;
    return 0;
}
 
  • 让我深有体会的是,jim的用Polish写的注释,直接看吐写,有些连GG都没翻译出来,以后所有的代码必须用英文写注释,这对同事是一种尊重,也是一个开发者的基本素质。当然自己的非正式笔记可以用中文,还要注意注释的正规,这个我做的很差,写的注释就像笔记一样,到处乱涂,里面随处可见take care,shit, fuck之类的口语!加油了,最大流,二分come on!

Advertisements