次最短路+概率

今天补了一道之前的次最短路问题。

第一次接触的次最短路是寒假...刚刚找了一波没找到，还发现好多题陌生了==！

POJ3255
题意很简单，就是让你求出次短路的距离。

分析：最开始的时候是按照寒假的思路，一个邻接矩阵记录边；最短路用Dijistra求，同时记录最短路的路径；然后将路径中的一段路距离改为INF，一直调用Dijistra。超内存了。
优化：邻接表记录边信息，记录路径时防止RE，就改为手写栈，超时了。
再优化：看别人题解才知道，Dijistra的优化是用优先队列（小根堆）来的==。
这次的代码主要就是注意一个细节两种情况：
1.如果取出的这个点u到v的距离d2比最短路（dist[v]）还短，那么就应该把最短路(dist[v)]赋值给次短路(dist2[v])，同时更新最短路的值。
2.如果取出的这个点u的距离比最短路长但是比次短路短，那么就应该赋值给次短路。
这两种情况因为都存在更新，所以必须都加入队列。

#include<bits/stdc++.h>

#define ll long long
#define CLR(x) memset(x,0,sizeof(x))
#define MEM(a,x) memset(a,x,sizeof(a))

const int INF = 0x3f3f3f3f;

const int maxn = 100000+100;

using namespace std;

struct node{
    int to,cost;
    node(int _to,int _cost){
        to=_to; cost=_cost;
    }
    node(){}
};

int n,r;
int dist[5050],dist2[5050];

typedef pair<int,int>P;
vector<node>V[5050];

void Dijistra(){
    priority_queue<P ,vector<P>,greater<P> >pq;
    fill(dist,dist+n,INF); fill(dist2,dist2+n,INF);
    dist[0]=0;
    pq.push(P(0,0));
    while(!pq.empty()){
        P p=pq.top(); pq.pop();
        int v=p.second,d=p.first;
        if(dist2[v]<d) continue;
        for(int i=0;i<V[v].size();i++){
            node e=V[v][i];
            int d2=d+e.cost;
            if(dist[e.to]>d2){
                swap(dist[e.to],d2);
                pq.push(P(dist[e.to],e.to));
            }
            if(dist2[e.to]>d2 && dist[e.to]<d2){
                dist2[e.to]=d2;
                pq.push(P(dist2[e.to],e.to));
            }
        }
    }
    printf("%d\n",dist2[n-1]);
}

int main()
{
    //FILEIN
    //FILEOUT
    //std::ios::sync_with_stdio(false);
    while(scanf("%d%d",&n,&r)!=EOF){
        node now;
        for(int i=0;i<r;i++){
            int from;
            scanf("%d%d%d",&from,&now.to,&now.cost);
            from--;
            now.to--;
            V[from].push_back(now);
            swap(now.to,from);
            V[from].push_back(now);
        }
        Dijistra();
    }
    return 0;
}

概率的题是HDU5236（系统维护，下次补链接）。
题意：有一个长度为n的字符，现在已知，每一秒钟可能发生三件事，1.成功输入一个字符（概率为1-p） 2.记录当前输入位置（按下x字符） 3.系统崩了，必须回到上次记录的位置（概率为p，上次记录不存在则回到初始）。问：期望按下最小的字符数。

分析：首先假设不存在记录，那么按字符数目的概率就是下面的dp[i]=dp[i-1]+px(dp[i]+1)+(1-p) 然后考虑，我们观察程序中的dp表达式，可以轻易发现，dp是呈指数级增长的，所以（从图像？）要考虑当分段是均匀时最优。于是有了第二个for。最强的地方来了！！！！
i表示的是字符分为i段；
quto表示每一段的长度；
ex表示分了之后的剩余量。
我们知道要把ex分到quto里面，才能达到最均匀（不然会出现100%51=49的情况）。怎么分呢！其实由quto*i+ex=n就知道，将ex提quto份平分过去才是最好的！
在这里我们平分的想法就是（因为quto>ex）把ex分成ex份然后拿给quto。这样就能保证最后答案的最大值与最小值仅相差1.

#include<bits/stdc++.h>

const int maxn = 1e5+100;
using namespace std;

int kk=1;
double dp[maxn];

void Solve()
{
    int n,x;
    double p;
    scanf("%d%lf%d",&n,&p,&x);
    dp[0]=0; double ans=INF;
    for(int i=1;i<=n;i++) dp[i]=(1+dp[i-1])/(1-p);
    for(int i=1;i<=n;i++){
        int quto=n/i;
        int ex=n%i;
        ans=min(ans,dp[quto+1]*ex+dp[quto]*(i-ex)+x*i);
    }
    printf("Case #%d: %.6f\n",kk++,ans);
}

int main()
{
    //FILEIN
    //FILEOUT
    //std::ios::sync_with_stdio(false);
    int Case=1,cases;
    scanf("%d", &Case); cases=Case;
    while(Case--){
        //printf("Case #%d:",cases-Case);
        Solve();
    }
    return 0;
}