POJ 2186

Tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100000+10;
/*
  有n只牛,牛之间存在一些关系,比如a认为b很受欢迎
,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据
给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?

解:
  对于一个有向无环图来说,其中有且仅有一个点出度为零
,那么这个特殊的点,可以由其他任何点到达。那么接下来我
们直接对所给的图进行强连通分量划分,然后把每个强连通分
量看做一个点,判定出度为零的点有几个,如果有一个就输出
这个点对应的强连通分量含有的节点个数,否则为零。
*/
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int vis[maxn];

stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    ///如果点从1开始计数,这里改成-1即可
    G[u-1].push_back(v-1);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    ///缩点,同一scc缩到同一点中
    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j){
            ///如果i到G[i][j]这条边不在强连通分量中
            ///说明是一个连接外面的点
            if(sccno[i]!=sccno[G[i][j]]){
                vis[sccno[i]]++;
            }
        }
    }

    int sum=0,ans=0,cnt=0;
    for(int i=1;i<=scc_cnt;++i){
        if(!vis[i]){
            ///如果出度是0,则是一个边界点
            sum++;
            ans=i;
        }
    }
    ///如果只有一个点的话,代表存在一个万人敬仰团体
    if(sum==1){
        for(int i=0;i<n;++i){
            if(sccno[i]==ans){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }else{
        printf("0\n");
    }
    return 0;
}
/*
3 3
1 2
2 1
2 3

1
*/

牛客练习赛 12 A,B

Link

https://www.nowcoder.net/acm/contest/68#question

题目都很易懂

第一题题解

把弧度值当角度来做即可,如果弧度是负数,把它转换成顺时针下的弧度值即可, 那么如果 a-b\<0则代表b在a顺时针前面,否则是a在b顺时针之前

然后分情况讨论即可,即钝角和锐角的情况

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    double a,b;
    int t;
    cin>>t;
    while(t--){
        cin>>a>>b;
        if(a<0.0) a=M_PI+a;
        if(b<0.0) b=M_PI+b;
        double rg=a-b,rt=abs(rg);
        if(rt>M_PI){
            if(rg>0.0){
                printf("counterclockwise\n");
            }else{
                printf("clockwise\n");
            }
        }else{
            if(rg>0.0){
                printf("clockwise\n");
            }else{
                printf("counterclockwise\n");
            }
        }
    }
    return 0;
}

第二题题解

我们将vis数组设为两重,一重是有钥匙,一重是无钥匙

vis[has_key?1:0][x][y]

bfs即可

代码

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

typedef struct Node{
    int has_key;
    int cnt,x,y;
}node;

char mp[510][510];
int h,w,sx,sy;
//об,ио,ср,вС
int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int vis[2][600][600];

void bfs(){
    bool yes=false;
    queue<node> st;
    st.push((Node){0,0,sx,sy});
    vis[0][sx][sy]=1;
    while(!st.empty()){
        node nd=st.front();st.pop();
        if(mp[nd.x][nd.y]=='E'){
            printf("%d\n",nd.cnt);
            return;
        }
        if(mp[nd.x][nd.y]=='K'){
            nd.has_key=1;
        }
        int nx,ny;
        for(int i=0;i<4;++i){
            nx=nd.x+mv[i][0],ny=nd.y+mv[i][1];
            if(vis[nd.has_key][nx][ny]) continue;
            if(mp[nx][ny]=='W') continue;
            if(mp[nx][ny]=='D' && !nd.has_key) continue;
            vis[nd.has_key][nx][ny]=1;
            st.push((Node){nd.has_key,nd.cnt+1,nx,ny});
        }
    }
    printf("-1\n");
}

int main(){
    cin>>h>>w;
    bool flag=true;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<h;++i){
        scanf("%s",mp[i]);
        for(int j=0;flag && j<w;++j){
            if(mp[i][j]=='S'){
                sx=i,sy=j;
                flag=false;
            }
        }
    }
    bfs();
    return 0;
}

Tarjan 强连通分量算法

Lrj中还说了一种求强连通分量的算法: Kosaraju算法.
但Tarjan算法的常数比Kos小,所以作为常用算法,我们直接学习Tarjan算法即可.

学习契机: HDU 6038

首先介绍下:

强连通分量:

画图以明志 —

Tarjan算法的时间复杂度是线性的,而kos算法则需要计算图的转置.该算法由Tarjan于1972年提出,是SCC(Strongly Connected Componenet,强连通分量)的第一个线性算法,Tarjan算法借助于DFS,但它并不需要靠遍历顺序(Kos算法的思想)来分离SCC,而是允许SCC并存于同一颗DFS树中,然后通过某种手段将他们分开.

DAG:

如果把一个集合看成一个点,那么所有的SCC构成了一个SCC图.这个SCC图不会存在有向环,因此是一个DAG(Directed Acyclic Graph,有向无环图).
那他喵的什么是DAG呢?我把上面的那个强连通分量图给DAG化:

算法流程

考虑强连通分量C,设其中第一个被发现的点为x,则C中其他点都是x的后代.我们希望在x dfs访问完成后立即输出C.这样,就可以在一棵DFS树中区分开所有SCC了.因此,问题的关键是如何发现每个SCC的第一个点.

如何判断是否是SCC顶点


假设我们正在判断u是否为某SCC的第一个被发现节点.如果我们发现从u的子节点出发可以达到u的祖先w,显然u就不是SCC的顶点.反之,如果SCC最远的顶点可以到u,则u是SCC的顶点.图中虚线表示一条或多条边和点.
我们使用两个数组来记录每个节点的状态.pre[]和lowlink[].
当递归回溯时如果这两个数组的值相同,则表明该节点为某SCC顶点.

证明

见: http://blog.csdn.net/keyboarderqq/article/details/71308102

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;

vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    printf("SCC个数: %d\n",scc_cnt);

    for(int i=0;i<n;++i){
        printf("点 %d 的 SCC 编号是: %d\n",i,sccno[i]);
    }
    return 0;
}
/*
6 6

1 0
0 4
4 5
5 1
1 2
2 3
*/

此致:画个图你就知道low数组的具体作用了.

2017 杭电多校训练赛 补题

第一场

1003 Colorful Tree hdoj6035

题意: 给定一棵树,树上各点之间的距离定义为 两点路线上不同颜色的个数。求这课数上n*(n-1)/2(即所有)的路径长度之和。
题解: (来自网络)
** //思路**:Answer = 所有颜色种类 * 所有路径数量 – 每一种颜色有多少路径没有经过 .

一开始假设每条路径都经过了所有颜色,再把每种颜色没经过的路径数减去就行,这个应该很好理解。问题是怎么算没经过的路径数?操作是这样的,如果算颜色1没经过的路径数,我们先把图里所有颜色是1的节点遮起来(假设这个点不存在,图在这个点是断路),图就被分成了很多块,每块的值= 那一块里的顶点数*(那一块里的顶点数-1)/2
所有块的值加起来就是不经过颜色1的所有路径数。

到这里是不是还是很好理解,那么问题来了,怎么实现?…题解里说用虚树什么的…

用一个DFS即可,复杂度O(n)

用Size数组储存以每个节点为根节点的子树大小(即子树里节点的个数),Sum数组…很难解释,大概是表示以每种颜色为根节点的子树的大小和,但不是非常准确,如果以颜色2为根节点的子树里还含有颜色为2的节点,那只要算根节点这个颜色为2的子树大小即可,若在以这个颜色为2的点为根节点的子树之外还有颜色为2的点,那还要加上这个点的值…不知道能不能理解…解释不清楚,大概就这个意思…

以下图颜色2为例,代码里最后的for里(即以根第一个节点计算中)减去的(n-sum[2])*(n-sum[2]-1)/2的那部分减去的是下图橙色圈里的那块,dfs里减去pp那部分是下图里蓝色圈的那块。其他具体的按照自己的理解再思考思考。

#include<bits/stdc++.h>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
//c[]数组是每个节点的颜色
int c[maxn],head[maxn],len,sum[maxn],size[maxn],vis[maxn];
LL d;
//边表
//邻接表
struct node{
    int v,next;
}p[maxn<<1];

void addedge(int u,int v){
    //有向边指向点的编号
    p[len].v=v;
    //每条边的下一条边是上一次纪录的边的号码
    p[len].next=head[u];
    //邻接表的方法
    //len为当前边的编号

    //只记录当前节点的最后一个边的位置
    head[u]=len++;
}
//对树进行dfs
void dfs(int x,int fa){
    //非这个点为根的所有该颜色的点
    LL pre=sum[c[x]];
    //size数组是当前节点的子节点总数目
    size[x]=1;
    int add=0;
    //通过邻接表对当前节点x进行dfs
    //等于0则退出
    for(int i=head[x];~i;i=p[i].next){
        //如果遇到反向边了,跳过,继续往其他边走
        if(p[i].v==fa)
            continue;
        dfs(p[i].v,x);
        size[x] += size[p[i].v];
        //计算当前节点子树所有和当前节点颜色不同的点的个数
        LL count = size[p[i].v] - sum[c[x]] + pre;
        pre = sum[c[x]];
        //当前子树的不同颜色点的个数
        add += count;
        //假设其他颜色都是白色,d即等于不同颜色所组成的边的总个数
        d += count*(count-1)>>1;
    }
    //计算以x为根节点子树的所有与x不同颜色的点的个数
    sum[c[x]] += add + 1;
}

int main(){
    int n,tcase=1;
    while(~scanf("%d",&n)){
        memset(head,-1,sizeof(head));
        memset(sum,0,sizeof(sum));
        memset(vis,0,sizeof(vis));
        d=len=0;
        LL number = 0;
        for(int i=1;i<=n;++i){
            scanf("%d",&c[i]);
            //记录颜色,颜色范围是[1,n]
            if(!vis[c[i]]){
                vis[c[i]]=1;
                number++;
            }
        }
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1,0);
        //ans初始等于(颜色个数)*(所有边的个数)-d(d为每个颜色在每个子树上被减去的不会经过那个颜色的路径的个数)
        LL ans=(number*(n-1)*n>>1)-d;
        for(int i=1;i<=n;++i){
            //不存在的颜色不需要计算,把已存在的颜色计算一下
            if(vis[i]&&i!=c[1]){
                //在根节点中与颜色i不同的颜色的个数
                LL count=n-sum[i];
                //每个颜色的路径数=(n*(n-1)>>1)-(count*(count-1)>>1)
                //以根节点为中心减去不同于当前颜色的路径的个数
                //最终得到的ans即为 每个颜色路径个数 的和
                ans-=count*(count-1)>>1;
            }
        }
        printf("Case #%d: %lld\n",tcase++,ans);
    }
    return 0;
}

1006 Function hdoj6038

这道题似懂非懂的写了出来…
大体是寻找循环节.
我写的代码有点乱…
原式为: f[i]=b[f[a[i]]]
A:{1,0,2} B{0,1}
可组成f: 000 111 110 001
A:{2,0,1} b{0,2,3,1}
可组成f: 000 231 312 123
以i -> a[i] i -> b[i] 为图的边进行Tarjan.
用Tarjan判断a和b各自有几个环(强连通分量),并且记录下每个环的大小.
然后AC代码如下(以后思路清楚了再重新看看…):

//HDU 6038
#include<bits/stdc++.h>

using namespace std;
const int maxn=100000+100;
const int mod=1e9+7;
typedef long long int lli;
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int a[maxn],b[maxn];

stack<int> S;
map<int,int> A,B;

//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

inline lli qp(lli aa,lli x){
    if(aa == 0) return 0;
    lli ans = 1;
    for(;x;x>>=1){
        if(x&1) ans = ans*aa % mod;
        aa = aa*aa % mod;
    }
    return ans % mod;
}

void dfs(int u,map<int,int>& T){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v,T);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            //未回溯时计算low数组需要通过pre数组
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        int cnt=0;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            cnt++;
            if(x==u)break;
        }
        T[cnt]++;
    }
}

void Tarjan(int n,map<int,int>& T){
    while(!S.empty()){
        S.pop();
    }
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i,T);
    }
}

int main(){
    int n,m,kase=0;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;++i){
            scanf("%d",&b[i]);
        }
        //对aTarjan
        for(int i=0;i<n;++i){
            addAdge(i,a[i]);
        }
        Tarjan(n,A);
        for(int i=0;i<n;++i){
            G[i].clear();
        }
        //对bTarjan
        for(int i=0;i<m;++i){
            addAdge(i,b[i]);
        }
        Tarjan(m,B);
        for(int i=0;i<m;++i){
            G[i].clear();
        }

        long long ans=1;
        map<int,int>::iterator it1;
        map<int,int>::iterator it2;
        for(it1=A.begin();it1!=A.end();it1++){
            long long tmp=0;
            for(it2=B.begin();it2!=B.end();it2++){
                if(it1->first%it2->first==0){
                    tmp=tmp+it2->second*it2->first;
                }
                //printf("%d %d : %d %d\n",it1->first,it2->first,it1->second,it2->second);
            }
            ans=ans*qp(tmp,it1->second)%mod;
        }
        printf("Case #%d: %lld\n",++kase,ans);
        A.clear();
        B.clear();
    }
    return 0;
}

1008 Hints of sd0061 hdoj6040

第二场

第三场

AOJ ALDS1_11_D Connected Components

Connected Components

Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

In the first line, two integer n and m are given. n is the number of users in the SNS and m is the number of relations in the SNS. The users in the SNS are identified by IDs 0, 1, …, n-1.

In the following m lines, the relations are given. Each relation is given by two integers s and t that represents s and t are friends (and reachable each other).

In the next line, the number of queries q is given. In the following q lines, q queries are given respectively. Each query consists of two integers s and t separated by a space character.

Output

For each query, print “yes” if t is reachable from s through the social network, “no” otherwise.

Constraints

  • 2 \leq n \leq 100,000
  • 0 \leq m \leq 100,000
  • 1 \leq q \leq 10,000

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no

求连通分量,对每一个连通分量进行染色.不在同一个联通分量的肯定无法联系.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
const int maxn=100000;
const int NIL=-1;
int n;
vector<int> G[maxn];
int color[maxn];

void dfs(int r,int c){
    stack<int> S;
    S.push(r);
    color[r]=c;
    while(!S.empty()){
        int u=S.top();S.pop();
        for(int i=0;i<G[u].size();++i){
            int v=G[u][i];
            if(color[v]==NIL){
                color[v]=c;
                S.push(v);
            }
        }
    }
}

void setColor(){
    int id=1;
    for(int i=0;i<n;++i){
        color[i]=NIL;
    }
    for(int u=0;u<n;++u){
        if(color[u]==NIL) dfs(u,id++);
    }
}

int main(){
    int s,t,m,q;

    cin>>n>>m;

    for(int i=0;i<m;++i){
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    setColor();

    cin>>q;
    for(int i=0;i<q;++i){
        cin>>s>>t;
        if(color[s]==color[t]){
            puts("yes");
        }else{
            puts("no");
        }
    }

    return 0;
}

Educational Codeforces Round 25 B

 【题目】

B. Five-In-a-Row

time limit: per test1 second
memory limit: per test256megabytes
input: standard input
output: standard output

Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it’s Alice’s turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.

Input

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters ‘X’ being a cross, letters ‘O’ being a nought and ‘.’ being an empty cell. The number of ‘X’ cells is equal to the number of ‘O’ cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.

Output

Print ‘YES’ if it’s possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print ‘NO’.

Examples
Input
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........
Output
YES
Input
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........
Output

NO

Link: http://codeforces.com/contest/825/problem/B
【题意】
X是否能在一步以内连成五子.可以则赢.

【题解】

数据量不大,枚举八个方向即可,注意,每次只能往一个方向走,不能拐弯.而且必须枚举八方向,不能只枚举向下的几个方向.
如果找到第一个五子,则往后就不需要计算了.

【Sourcr Code】
github: Educational Codeforces Round 25 B.cpp

#include<bits/stdc++.h>
using namespace std;
char mp[11][11];
bool re;
int d[8][3]={{0,1},{1,0},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};

bool check(int x,int i,int y,int j){
    if(x+i>=0&&x+i<10&&y+j>=0&&y+j<=10)
        return true;
    else return false;
}

void dfs(int x,int y,int win,int ct,int dir){
 //   if(dir==3)
 //       printf("(%d,%d):%d %d\n",x,y,win,dir);
    if(win==5 || re){re=true;return;}
    int i=d[dir][0],j=d[dir][1];
    if(check(x,i,y,j)){
        if(mp[x+i][y+j]=='X') dfs(x+i,y+j,win+1,ct,dir);
        if(mp[x+i][y+j]=='.' && ct==0) dfs(x+i,y+j,win+1,1,dir);
    }
}

int main(){
    re=false;
    for(int i=0;i<10;++i)
        gets(mp[i]);
    for(int i=0;i<10;++i){
        if(re)break;
        for(int j=0;j<10;++j){
            if(mp[i][j]=='X'){
                for(int k=0;k<8;++k){
                    dfs(i,j,1,0,k);
                    if(re)break;
                }
                if(re)break;
            }
        }
    }
    if(re)printf("YES\n");
    else printf("NO\n");
    return 0;
}

/**
....X.....
...X.OOOO.
..X.......
.X........
..........
..........
..........
..........
..........
..........
**/

PAT L3-005

【Tip】

Dijsktra模板题

【Code】

#include<bits/stdc++.h>
#define fill(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=30000;

int N,M,K,D;
char alpha1[100],alpha2[100];
int now,goal,di;
 
struct Edge{
    int from,to,dist;
};
struct HeapNode{  //Dijkstra算法用到的优先队列的节点
    int d,u;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m; //点数和边数
    vector<Edge> edges; //边列表
    vector<int> G[maxn]; //每个节点出发的边编号(从0开始编号)
    bool done[maxn];    //是否永久标号
    int d[maxn];        //s到各个点的距离
    int p[maxn];        //最短路中的上一条边

    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i) G[i].clear();//清空邻接表
        edges.clear();//清空边表
    }
    
    void AddEdge(int from,int to,int dist){
        //如果是无向图,每条无向边需调用两次AddEdge
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    
    void dijkstra(int s){//求s到所有点的距离
         priority_queue<HeapNode> Q;
         for(int i=0;i<n;++i) d[i]=INF;
         d[s]=0;
         fill(done);
         Q.push((HeapNode){0,s});
         while(!Q.empty()){
             HeapNode x=Q.top(); Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();++i){
                Edge &e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
         }
    }
};
int main(){
    while(~scanf(“%d%d%d%d”,&N,&M,&K,&D)){
        Dijkstra dj;
        dj.init(N+M);
        for(int i=0;i<K;++i){
            scanf(“\n%s %s %d”,alpha1,alpha2,&di);
            //因为可能出现G10 123等字符串
            //所以这里转换必须用atoi或stoi
            //后者是c11的
            if(alpha1[0]==’G’){
                now = N-1 + atoi(alpha1+1);
            }else
                now = atoi(alpha1)-1;
                
            if(alpha2[0]==’G’){
                goal = N-1 + atoi(alpha2+1);
            }else
                goal = atoi(alpha2)-1;
            
            dj.AddEdge(now,goal,di);
            dj.AddEdge(goal,now,di);
        }
        int ansid=-1,ansdis=INF;
        double ansave=INF;
        
        for(int i=0;i<M;++i){
            int index=i+N,mindis=INF;
            bool flag=true;
            double ave=0.0;
            dj.dijkstra(index);
            for(int j=0;j<N;++j){
                if(dj.d[j]>D){
                    flag=false;
                    break;
                }
                ave+=1.0*dj.d[j];
                mindis=mindis>dj.d[j]?dj.d[j]:mindis;
            }
            if(!flag)
                continue;
            else{
                if(ansdis==INF){
                    ave=ave/N;
                    ansave=ave;
                    ansid=i;
                    ansdis=mindis;
                }else if(mindis>ansdis){
                    ave=ave/N;
                    ansave=ave;
                    ansid=i;
                    ansdis=mindis;
                }else if(ansdis==mindis){
                    ave=ave/N;
                    if(ave<ansave){
                        ansave=ave;
                        ansid=i;
                        ansdis=mindis;
                    }else if(ave==ansave){
                        ansid=i>ansid?ansid:i;
                        ansdis=mindis;
                    }
                }
            }
        }
        
        if(ansid==-1)
            printf(“No Solution\n”);
        else{
            printf(“G%d\n”,ansid+1);
            printf(“%.1f %.1f\n”,1.0*ansdis,ansave);
        }
    }
    return 0;
}