codeforces 505 B. Mr. Kitayuta's Colorful Graph
http://codeforces.com/contest/505/problem/B 题意；给一个图，边有颜色。给q个查询，每个查询一对点x,y。问只经过某种颜色的边使得x能到y颜色数目。 思路：存颜色的时候卡了下。。本来打算开一个二维的set用来存颜色。。。没想明白。。后来发现。。还是用vecotr就好啊。。。多开一维度vector。。或者。。vector 用 pair 都是可以的。。。因为颜色数不多。。可以暴力枚举每种颜色做一遍dfs 看只走有这条颜色的边x能否到y。。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月07日 星期一 09时52分33秒
4File Name :code/cf/problem/505B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24#define pi pair<int ,int >
25typedef long long LL;
26
27
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=105;
35int n,m,q;
36vector<pi>edge[N];
37
38bool vis[N];
39
40
41void dfs (int x,int y,int col)
42{
43// cout<<"x:"<<x<<" col:"<<col<<endl;
44 vis[x] = true;
45 if (x==y) return;
46 for ( int i = 0 ; i < edge[x].size(); i++)
47 {
48 pi v = edge[x][i];
49// cout<<"to:"<<v.sec<<endl;
50 if (v.sec ==col &&!vis[v.fst])
51 dfs(v.fst,y,col);
52 }
53}
54int main()
55{
56 #ifndef ONLINE_JUDGE
57 freopen("code/in.txt","r",stdin);
58 #endif
59 scanf("%d %d",&n,&m);
60 for ( int i = 0 ; i < m ; i++)
61 {
62 int x,y,z;
63 cin>>x>>y>>z;
64 edge[x].push_back(make_pair(y,z));
65 edge[y].push_back(make_pair(x,z));
66 // cnt[x][y].insert(z);
67 // cnt[y][x].insert(z);
68 }
69 scanf("%d",&q);
70 for ( int i = 0 ; i < q ; i ++)
71 {
72 int u,v;
73 scanf("%d %d",&u,&v);
74 int res = 0 ;
75 for ( int j = 0 ; j <=100 ; j++) //把j++写成了i++,调了半小时2333
76 {
77 ms(vis,false);
78 dfs(u,v,j);
79 if (vis[v]) res++;
80 }
81 cout<<res<<endl;
82 }
83
84
85
86
87
88 #ifndef ONLINE_JUDGE
89 fclose(stdin);
90 #endif
91 return 0;
92}