Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Let G = (V, E) be a connected graph without loops and multiple edges, where V and E are the vertex and edge, respectively, sets of G. For any two vertices u, v V , the distance between vertices u and v in G is the number of edges in a shortest u - v path. A shortest path between u and v is called a u - v geodesic. Let I(u, v) denote the set of vertices such that a vertex is in I(u, v) if and only if it is in some u - v geodesic of G and, for a set S V , I(S) = I(u, v). A vertex set D in graph G is called a geodetic set if I(D) = V . The geodetic set problem is to verify whether D is a geodetic set or not. We use Figure 3 as an example. In Figure 3, I(2, 5) = {2, 3, 4, 5} since there are two shortest paths between vertices 2 and 5. We can see that vertices 3 and 4 are lying on one of these two shortest paths respectively. However, I(2, 5) is not a geodetic set since I(2, 5) V . Vertex set {1, 2, 3, 4, 5} is intuitively a geodetic set of G. Vertex set D = {1, 2, 5} is also a geodetic set of G since vertex 3 (respectively, vertex 4) is in the shortest path between vertices 1 and 5 (respectively, vertices 2 and 5). Thus, I(D) = V . Besides, vertex sets {1, 3, 4} and {1, 4, 5} are also geodetic sets. However, D = {3, 4, 5} is not a geodetic set since vertex 1 is not in I(D).

Input 

The input file consists of a given graph and several test cases. The first line contains an integer n indicating the number of vertices in the given graph, where 2n40. The vertices of a graph are labeled from 1 to n. Each vertex has a distinct label. The following n lines represent the adjacent vertices of vertex i, i = 1, 2,..., n. For example, the second line of the sample input indicates that vertex 1 is adjacent with vertices 2 and 3. Note that any two integers in each line are separated by at least one space. After these n lines, there is a line which contains the number of test cases. Each test case is shown in one line and represents a given subset D of vertices. You have to determine whether D is a geodetic set or not.

Output 

For each test case, output `yes' in one line if it is a geodetic set or `no' otherwise.

Sample Input 

5
2 3
1 3 4
1 2 5
2 5
3 4
6
1 2 3 4 5
1 2 5
2 4
1 3 4
1 4 5
3 4 5

Sample Output 

yes
yes
no
yes
yes
no

---

題目描述：

題目給定一張圖，根據定義 I(D) 去進行判斷，D 是一個點的集合，而 I(D) 表示從 D 中認抓兩個點出來作最短路徑，所有可能在路徑上的點集合。如果 I(D) = V 即所有點都可能在最短路徑上。

題目解法：

做一次 all-pair 最短路徑，窮舉 D 中的任兩點檢查最短路徑上有哪些點。

最後去檢查有沒有 = V。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
    int n, q;
    int i, j, k;
    char s[105];
    while(scanf("%d", &n) == 1) {
        while(getchar() != '\n');
        int g[50][50] = {};
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= n; j++) {
                g[i][j] = 0xffff;
            }
            g[i][i] = 0;
        }
        for(i = 1; i <= n; i++) {
            gets(s);
            int f = 0, tmp = 0;
            for(j = 0; s[j]; j++) {
                if(s[j] >= '0' && s[j] <= '9')
                    tmp = tmp*10 + s[j]-'0', f = 1;
                else {
                    if(f) {
                        g[i][tmp] = g[tmp][i] = 1;
                        tmp = 0, f = 0;
                    }
                }
            }
            if(f) {
                g[i][tmp] = g[tmp][i] = 1;
            }
        }
        for(k = 1; k <= n; k++)
            for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                    g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
        scanf("%d", &q);
        while(getchar() != '\n');
        while(q--) {
            gets(s);
            int f = 0, tmp = 0;
            int D[105], didx = 0;
            for(i = 0; s[i]; i++) {
                if(s[i] >= '0' && s[i] <= '9')
                    tmp = tmp*10 + s[i]-'0', f = 1;
                else {
                    if(f) {
                        D[didx++] = tmp;
                        tmp = 0, f = 0;
                    }
                }

            }
            if(f) {
                D[didx++] = tmp;
            }
            int I[105] = {};
            for(i = 0; i < didx; i++) {
                for(j = i; j < didx; j++) {
                    for(k = 1; k <= n; k++) {
                        if(g[D[i]][k] + g[k][D[j]] == g[D[i]][D[j]])
                            I[k] = 1;
                    }
                }
            }
            int ret = 1;
            for(i = 1; i <= n; i++)
                ret &= I[i];
            puts(ret ? "yes" : "no");
        }
    }
    return 0;
}