#include<bits/stdc++.h>

using namespace std;

const int N=;

int in[N],post[N],ans,mi;

void solve(int l,int r,int f,int s)

{

    if(l==r)return;

    if(r-l<=)

    {

        if(in[l]+s<mi)mi=in[l]+s,ans=in[l];

        return ;

    }

    for(int i=l;i<r;i++)

        if(in[i]==post[f])solve(i+,r,f-,s+post[f]),solve(l,i,f+i-r,s+post[f]);

}

int main()

{

    ios::sync_with_stdio(false);

    string s,c;

    while(getline(cin,s))

    {

        getline(cin,c);

        mi=<<;

        stringstream ss(s),sc(c);

        int n=;

        while(ss>>in[n])sc>>post[n++];

        solve(,n,n-,);

        cout<<ans<<"\n";

    }

    return ;

}

#include <stdio.h>

#include <string.h>

int pre[];

int post[];

int cc;

void calc(int a1,int b1,int a2,int b2)

{

    int i;

    if(a1>=b1)  return;

    for(i=a2; i<=b2-; i++)

    {

        if(pre[a1+] == post[i])  break;

    }

    if(i == b2-)  cc++;

    calc(a1+,a1++(i-a2),a2,i);

    calc(a1++(i-a2)+,b1,i+,b2-);

}

int a[];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=; i<n; i++)

        scanf("%d",&pre[i]);

    for(int i=; i<n; i++)

        scanf("%d",&post[i]);

    cc=;

    calc(,n-,,n-);

    n=cc;

    int sum=,i,k;

    for(i=; i<; i++)

        a[i]=;

    a[]=;

    for(k=; k<=n; k++)

    {

        for(i=; i<sum; i++)

            a[i]=a[i]*;

        for(i=; i<sum; i++)

            if(a[i]>=)

            {

                a[i+]=a[i+]+a[i]/;

                if(i+==sum)sum++;

                a[i]=a[i]%;

            }

    }

    for(i=sum-; i>=; i--)

        printf("%d",a[i]);

    printf("\n");

return ;

}

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

5 5

1 2 20

2 3 30

3 4 20

4 5 20

1 5 100

90

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

 

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

const int N=,INF=0x3f3f3f3f;

vector<pair<int,int> >G[N];

priority_queue<int>Q;

int dis[N];

int main()

{

    int n,m;

    cin>>m>>n;

    for(int i=,u,v,w;i<m;i++)

        cin>>u>>v>>w,G[u].push_back(make_pair(w,v)),G[v].push_back(make_pair(w,u));

    vector<pair<int,int> >::iterator it;

    fill(dis,dis+n+,INF);

    dis[]=,Q.push();

    while(!Q.empty())

    {

        int u=Q.top();

        Q.pop();

        for(it=G[u].begin();it!=G[u].end();it++)

            if(dis[u]+it->first<dis[it->second])dis[it->second]=dis[u]+it->first,Q.push(it->second);

    }

    cout<<dis[n];

}

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping. 
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. 
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence. 
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.

The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.

For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

2

0 0

3 4

3

17 4

19 4

18 5

0

Scenario #1

Frog Distance = 5.000

Scenario #2

Frog Distance = 1.414

#include <stdio.h>

#include <algorithm>

#include <math.h>

using namespace std;

#define fi first

#define se second

const int MAXN=;

pair<int,int>p[MAXN];

double dis(pair<int,int>p1,pair<int,int>p2) {

    return (p1.fi-p2.fi)*(p1.fi-p2.fi)+(p2.se-p1.se)*(p2.se-p1.se);

}

int dist[MAXN][MAXN];

int main() {

    int n,cas=;

    while(~scanf("%d",&n)) {

        if(!n)break;

        for(int i=; i<n; i++) {

            int x,y;

            scanf("%d%d",&x,&y);

            p[i]=make_pair(x,y);

        }

        for(int i=; i<n; i++)

            for(int j=i; j<n; j++) {

                dist[j][i]=dist[i][j]=dis(p[i],p[j]);

            }

        for(int k=; k<n; k++)

            for(int i=; i<n; i++)

                for(int j=; j<n; j++)

                    if(dist[i][j]>max(dist[i][k],dist[k][j]))

                        dist[i][j]=max(dist[i][k],dist[k][j]);

        printf("Scenario #%d\n",cas++);

        printf("Frog Distance = %.3f\n\n",sqrt(dist[][]*1.0));

    }

    return ;

}

Given a n*n matrix C _ij (1<=i,j<=n),We want to find a n*n matrix X _ij(1<=i,j<=n),which is 0 or 1.

Besides,X _ij meets the following conditions:

1.X ₁₂+X ₁₃+...X _1n=1 
2.X _1n+X _2n+...X _n-1n=1 
3.for each i (1<i<n), satisfies ∑X _ki (1<=k<=n)=∑X _ij (1<=j<=n).

For example, if n=4,we can get the following equality:

X ₁₂+X ₁₃+X ₁₄=1 
X ₁₄+X ₂₄+X ₃₄=1 
X ₁₂+X ₂₂+X ₃₂+X ₄₂=X ₂₁+X ₂₂+X ₂₃+X ₂₄ 
X ₁₃+X ₂₃+X ₃₃+X ₄₃=X ₃₁+X ₃₂+X ₃₃+X ₃₄

Now ,we want to know the minimum of ∑C _ij*X _ij(1<=i,j<=n) you can get.

4

1 2 4 10

2 0 1 1

2 2 0 5

6 3 1 2

3

#include <stdio.h>

#include <queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int N=;

int n,g[N][N],dis[N],dis1[N];

int dij(int s)

{

    fill(dis,dis+N,INF);

    priority_queue<int> pq;

    dis[s]=,pq.push(s);

    while(!pq.empty())

    {

        int u=pq.top();

        pq.pop();

        for(int i=;i<=n;i++)

        if(dis[i]>dis[u]+g[u][i])dis[i]=dis[u]+g[u][i],pq.push(i);

    }

}

int dij1(int s)

{

    fill(dis1,dis1+N,INF);

    priority_queue<int> pq;

    dis1[s]=,pq.push(s);

    while(!pq.empty())

    {

        int u=pq.top();

        pq.pop();

        for(int i=;i<=n;i++)

            if(dis1[i]>dis1[u]+g[i][u])dis1[i]=dis1[u]+g[i][u],pq.push(i);

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        for(int i=; i<=n; i++)

        {

            for(int j=; j<=n; j++)

                scanf("%d",&g[i][j]);

            g[i][i]=INF;

        }

        dij(),dij1();

        int mi1=INF,mi=dis[n],mi2=INF;

        for(int i=;i<=n;i++)

            mi1=min(dis[i]+dis1[i],mi1);

        dij(n),dij1(n);

        for(int i=;i<n;i++)

            mi2=min(dis[i]+dis1[i],mi2);

        printf("%d\n",min(mi,mi1+mi2));

    }

    return ;

}

#include <stdio.h>

#include <queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int N=;

int n,g[N][N],dis[N];

bool did[N];

int dij(int s,int t)

{

    for(int i=; i<=n; i++)

    {

        if(i!=s)dis[i]=g[s][i];

        else dis[i]=INF;

        did[i]=;

    }

    int c=;

    while(c<n)

    {

        int mi,m=INF;

        for(int i=; i<=n; i++)

            if(!did[i]&&dis[i]<m)

            {

                m=dis[i];

                mi=i;

            }

        did[mi]=;

        for(int i=; i<=n; i++)

            if(!did[i]&&dis[i]>dis[mi]+g[mi][i])

            {

                dis[i]=dis[mi]+g[mi][i];

            }

        c++;

    }

    return dis[t];

}

int main()

{

    while(~scanf("%d",&n))

    {

        for(int i=; i<=n; i++)

            for(int j=; j<=n; j++)

            {

                scanf("%d",&g[i][j]);

            }

        printf("%d\n",min(dij(,n),dij(,)+dij(n,n)));

    }

    return ;

Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).

Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

Line 1: Three space-separated integers: N, ML, and MD.

Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

4 2 1

1 3 10

2 4 20

2 3 3

27

Explanation of the sample:

There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.

The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.

差分约束，这个还是很难的

InputThere are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an " I" followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a "Q", then you need to output the kth great number. 
OutputThe output consists of one integer representing the largest number of islands that all lie on one line. 
Sample Input

8 3

I 1

I 2

I 3

Q

I 5

Q

I 4

Q

Sample Output

1

2

3

Hint

Xiao  Ming  won't  ask  Xiao  Bao  the  kth  great  number  when  the  number  of  the  written number is smaller than k. (1=<k<=n<=1000000).

---

题目还是挺简单易懂的，就是有insert还有query操作

但是可能是重复的，所以multiset