今天补了一道之前的次最短路问题。
第一次接触的次最短路是寒假...刚刚找了一波没找到，还发现好多题陌生了==！
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;
}
