Input:
The first line contains three integers n, m, k (2 ≤ n ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105). Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ xi ≤ 109). Each of the next k lines contains two integers si and yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109). It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital.
Output:
Output a single integer representing the maximum number of the train routes which can be closed.
Example:
Input 5 5 3 1 2 1 2 3 2 1 3 3 3 4 4 1 5 5 3 5 4 5 5 5 Output 2 Input 2 2 3 1 2 2 2 1 3 2 1 2 2 2 3 Output 2
题意：
假设你是某国（女儿国^_^）的主席，现在你为了省钱想去掉一些没用的铁路，给出城市数N，土路数量M和长度，铁路数量K和长度， 让你去掉那些不影响最小路径的铁路，问最多能去几条?
题目确定1号城市为首都，所有铁路都是从首都出发到其他城市的。
思路：
先记录下所有铁路的信息，再把铁路和土路全部记录到邻接表中然后Spfa求单源（点1）最短路径并记录最短路径数量，再与铁路比较。
如果到某点的最短距离小于铁路，那么这条铁路直接去掉，如果等于则判断最短路径数量是否为一，如果不唯一代表有其他路则这条铁路也去掉。
这题有一个点注意就是铁路要去重。
还有记录边的长度要用long long。
代码：
#include<iostream> #include<cstring> #include<cmath> #include<stdio.h> #include<queue> #include<vector> #define INF 1000000070000 typedef long long ll; using namespace std; int N,M,K; ll len[100005][2]; struct D { int to; ll lenth; D(int a,ll b) { to = a; lenth = b; } }; vector<D>map[100005]; bool mark[100005]; void Spfa() { for(int i=2 ; i<=N ; i++) { len[i][0] = INF; len[i][1] = 0; } len[1][0] = len[1][1] = 0; queue<int>Q; Q.push(1); mark[1] = true; while(!Q.empty()) { int mid = Q.front(); Q.pop(); mark[mid] = false; vector<D>::iterator it; for(it = map[mid].begin() ; it!=map[mid].end() ; it++) { if(len[(*it).to][0]>len[mid][0] + (*it).lenth) { len[(*it).to][0] = len[mid][0] + (*it).lenth; len[(*it).to][1] = 0; if(mark[(*it).to] == false) { Q.push((*it).to); mark[(*it).to] = true; } } else if(len[(*it).to][0] == len[mid][0] + (*it).lenth)len[(*it).to][1]++; } } } int sum; int main() { scanf("%d %d %d",&N,&M,&K); while(M--) { int a,b; ll c; scanf("%d %d %lld",&a,&b,&c); map[a].push_back(D(b,c)); map[b].push_back(D(a,c)); } /*Spfa(); ll len1[N+1][2]; for(int i=1 ; i<=N ; i++) { len1[i][0] = len[i][0]; len1[i][1] = len[i][1]; }*/ ll mid[N+1]; memset(mid,0,sizeof(mid)); while(K--) { int a; ll b; scanf("%d %lld",&a,&b); if(mid[a] == 0)mid[a] = b; else { if(mid[a]>b)mid[a] = b; sum++; } } for(int i=2 ; i<=N ; i++) { if(mid[i] == 0)continue; map[1].push_back(D(i,mid[i])); map[i].push_back(D(1,mid[i])); } Spfa(); for(int i=2 ; i<=N ; i++) { if(mid[i]!=0) { if(len[i][0]<mid[i])sum++; else if(len[i][0] == mid[i]) { if(len[i][1]>0)sum++; } } } printf("%d\n",sum); return 0; }
