今天補了一道之前的次最短路問題逼纸。

第一次接觸的次最短路是寒假...剛剛找了一波沒找到嗅蔬，還發(fā)現(xiàn)好多題陌生了==歌亲！

POJ3255
題意很簡單菇用，就是讓你求出次短路的距離。

分析：最開始的時候是按照寒假的思路陷揪，一個鄰接矩陣記錄邊惋鸥；最短路用Dijistra求杂穷，同時記錄最短路的路徑；然后將路徑中的一段路距離改為INF卦绣，一直調(diào)用Dijistra耐量。超內(nèi)存了。
優(yōu)化：鄰接表記錄邊信息滤港，記錄路徑時防止RE廊蜒，就改為手寫棧，超時了溅漾。
再優(yōu)化：看別人題解才知道山叮，Dijistra的優(yōu)化是用優(yōu)先隊列（小根堆）來的==。
這次的代碼主要就是注意一個細節(jié)兩種情況：
1.如果取出的這個點u到v的距離d2比最短路（dist[v]）還短樟凄，那么就應(yīng)該把最短路(dist[v)]賦值給次短路(dist2[v])聘芜，同時更新最短路的值。
2.如果取出的這個點u的距離比最短路長但是比次短路短缝龄，那么就應(yīng)該賦值給次短路汰现。
這兩種情況因為都存在更新，所以必須都加入隊列叔壤。

#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（系統(tǒng)維護瞎饲，下次補鏈接）。
題意：有一個長度為n的字符炼绘，現(xiàn)在已知嗅战，每一秒鐘可能發(fā)生三件事，1.成功輸入一個字符（概率為1-p） 2.記錄當(dāng)前輸入位置（按下x字符） 3.系統(tǒng)崩了俺亮，必須回到上次記錄的位置（概率為p驮捍，上次記錄不存在則回到初始）。問：期望按下最小的字符數(shù)脚曾。

分析：首先假設(shè)不存在記錄东且，那么按字符數(shù)目的概率就是下面的dp[i]=dp[i-1]+px(dp[i]+1)+(1-p) 然后考慮，我們觀察程序中的dp表達式本讥，可以輕易發(fā)現(xiàn)珊泳，dp是呈指數(shù)級增長的，所以（從圖像拷沸？）要考慮當(dāng)分段是均勻時最優(yōu)色查。于是有了第二個for。最強的地方來了Ｗ采帧Ｑ砹恕！勤庐！
i表示的是字符分為i段示惊；
quto表示每一段的長度好港；
ex表示分了之后的剩余量。
我們知道要把ex分到quto里面米罚，才能達到最均勻（不然會出現(xiàn)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;
}