1、wander

这道题是一道基于贝尔曼·福特算法的求带权最短路的一道升级版的题，主要运用了贝尔曼福特算法，以及一条带权边的删除。

思路：体面意思明显就是要求一个最短路，并且用special judge 来给了部分分，然而某不愿意透露姓名的蒟蒻（我）仍然毅然决然地丢了部分分orz。。。（面壁）。

    总而言之就是先把邻接表建起来，注意其中因为不仅要生长出编号，还要有权值的保存，所以在VtxHead这个结构体中用了一个结构体函数来进行生长操作。然后就是贝尔曼·福特算法的优先队列优化版，求出最短路。

如果要得%40的分做到这应该就能拿到了，但要得全分还得“闪现”（也就是删一条边）进行一波操作：

    首先我们可以建一个反路径。

    我们可以知道：删去一条边之后的最短路就相当于从出发点（eg：1）到某点，以及本来与某点连着的另一点到终点的长度之和。

    基于此我们可以对每一个点进行枚举，贪心求出最小的删边策略。

这样100分就到手了！

代码稍微复杂了点：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;


struct Main {
struct Vtx {
int To;
long long Wgt;
Vtx *Next;

Vtx(void) : Next(NULL) {}
Vtx(int To, long long Wgt) : 
To(To), Wgt(Wgt), Next(NULL) {}
};

struct VtxHead : Vtx {
Vtx *Head;
long long Dist;

void Grow(int To, long long Wgt)
{
if (Head) Next = 
Next->Next = new Vtx(To, Wgt);
else Head = 
Next = new Vtx(To, Wgt);
}

VtxHead(void) : Head(NULL),
Dist(LLONG_MAX) {}
} G[MAXN], AntiG[MAXN];

struct Unit {
int u;
long long Dist;

bool operator < (const Unit &x) const
{
return Dist > x.Dist;
}
};

inline void Search(VtxHead *Graph, int Source)
{
priority_queue<Unit> Travel;
Travel.push( (Unit) { Source, 0 } );
Graph[Source].Dist = 0;

while (!Travel.empty()) {
int From = Travel.top().u;
long long CrtDist = Travel.top().Dist;
Travel.pop();

if (CrtDist <= Graph[From].Dist)
for (register Vtx *i = Graph[From].Head;
i; i = i->Next) // i->To
if (Graph[From].Dist + i->Wgt <
Graph[i->To].Dist) {
Graph[i->To].Dist = 
Graph[From].Dist + i->Wgt;

Travel.push( 
(Unit) { i->To, Graph[i->To].Dist } );
}
}
}

Main(void)
{
int n, m;
scanf("%d %d", &n, &m);

while (m--) {
int u, v;
long long Wgt;
scanf("%d %d %lld", 
&u, &v, &Wgt);

G[u].Grow(v, Wgt);
AntiG[v].Grow(u, Wgt);
}


Search(G, 1);
Search(AntiG, n);

printf("%lld\n", G[n].Dist);

long long MinDist = G[n].Dist;
for (register int i = 1; i <= n; ++i)
for (register Vtx *j = G[i].Head;
j; j = j->Next)
if (G[i].Dist + AntiG[j->To].Dist <
MinDist)
MinDist = 
G[i].Dist + AntiG[j->To].Dist;

printf("%lld\n", MinDist);
}
};


int main(void)
{
delete new Main;

return 0;

}

（改着改着就变得跟tot差不多了，，，但是5分了好久特别气。。）

2、Gene

（为什么生竞大神会来找我们。。。。）

此题其实是一道阅读理解题，总而言之就是要你对几组数据进行排序，只是分开说了三个优先级关键点：

    最高：长度短

    次之：字典序大

    最次：编号小

题中给的数据都是约等于，用动态数组vector不仅可以方便地储存数，还可以快捷地比较字典序。

主要就是排序，如上所述。

题是简单的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 10005
int n;
struct lian{
int lenth;
int order;
vector<int> l;
}lis[MAXN];
bool cmp(lian x,lian y)
{
if(x.lenth != y.lenth)
return x.lenth < y.lenth;
else{
if(x.l == y.l)
return x.order < y.order;
else{
return x.l > y.l;
}
}
}
int main()
{
// cin >> n;
scanf("%d",&n);
for(int i = 0;i < n;i++)
{
scanf("%d",&lis[i].lenth);
lis[i].order = i;
for(int j = 0;j < lis[i].lenth;j++)
{
int num;
scanf("%d",&num);
lis[i].l.push_back(num);
}
}
sort(lis,lis + n,cmp);
for(int i = 0;i < n;i++)
{
if(i == n-1)
{
printf("%d",lis[i].order + 1);
return 0;
}
printf("%d ",lis[i].order + 1);
}

} 

3、joseph

经典的joseph问题，可以看到数据规模十分坑爹，所以常规方法肯定是有问题的，这里我们用了数学方法。

我们对整个报数过程做一个梳理：

    可以看出，每次出圈的人都是m%n（n为当前人数）编号的人，这里我们有先见之明地把序号变成从0开始。

    为什么呢？ 因为方便我们求模啊！不然7%7等于0这种事十分尴尬。

那么这时出圈的人就是m%n - 1了，这时他的下一个就是（假设为）k = m%n，此时k就成为了新一轮的起始“0”。

现在我们把他们的编号做一下转换：
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x
是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变

回去的公式很简单：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？显然，只要知道(n-2)个人的解就行了。(n-2)个人的解
呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！
递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

有一点值得注意的是：原题中数据有个十分变态的20%n达到了10^9，但是m固定为2

    这肯定是要我们找规律了！

    如果m=2意味着什么？

    是的，每次少一半的人，并且两两分组，如果n为2的x次方的话，剩下肯定是第一个元素。

那么，我们只需要知道离n最近的小于n的2^x方，算出差值s，找到那起始的元素编号就行了。

    起始编号是什么呢？ 当然是2s+1啦！

于是100分到手。

程序：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n,m;

int main()
{
//#ifndef LOCAL
// freopen("joseph.in", "r", stdin);
// freopen("joseph.out", "w", stdout);
//#endif//文件读入用
int i,ans = 0;
scanf("%lld %lld",&n,&m);

if(m == 2)
{
LL t = 1;
while((t << 1) <= n) t <<= 1;
printf("%lld",(n - t) * 2 + 1);
return 0;
}
for(i = 2;i <= n;i++)
{
ans = (ans + m) % i;
}
printf("%lld",ans + 1);
return 0;
}