国庆集训DAY2

谈谈今天的题目。

第一题简单题,两个单元最短路然后选择一个最短组合。

第二题打爆力60分,(正解比较难思考)

第三、第四题,我根本看不懂……

综上,我也不知道我怎么弄的样例分。

中转站

算一个模板题。按上面的说法做就完了。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct node{
    ll u,v,w;
    ll next;
}zz[2*M];
void jy(ll u,ll v,ll w)
{
    pos++;
    zz[pos].u = u;
    zz[pos].v = v;
    zz[pos].w = w;
    zz[pos].next = head[zz[pos].u];
    head[zz[pos].u] = pos;
    return;
}

priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
ll dis[N];
ll vis[N];
void Dij(ll from)
{
    ll u;
    for(int i=1;i<=n;i++)
    {
        dis[i]=1e13;vis[i] = 0;
    }
       
    dis[from] = 0;
    q.push(make_pair(0,from));
    while(!q.empty())
    {
        u = q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(ll i=head[u];i;i=zz[i].next)
        {
            if(dis[zz[i].v]>dis[zz[i].u]+zz[i].w)
            {
                dis[zz[i].v] = dis[zz[i].u]+zz[i].w;
                q.push(make_pair(dis[zz[i].v],zz[i].v));
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        if(from==s)c[r[i]] = dis[r[i]];
        else ans = min(ans,c[r[i]]+dis[r[i]]);
    }
    return;
}

粒子自撞机

一个数学题。

用扩展欧几里得来求正解。

这是欧几里得模板

正解我也不会。

 

 

发表评论

邮箱地址不会被公开。 必填项已用*标注