• 题目链接：http://codeforces.com/problemset/problem/450/D

• 题目大意： 给定一个无向图，其中从起点1开始到其他的点 i 有路相连。同时从1开始还有特殊的边连向i。现在问，最多能删除多少条特殊的边，使得这个无向图从起点出发到其他任意点的最短路径不变。

• 思路： 比较显然的是这道题目不能用 $O(n^2)$ 的dij最短路来做，我们需要用一个优先队列来优化成 $O(mlogn)$ 的最短路。比较直观的想法是，在每次的 $pop$ 操作之后，判断这个点是否合法。然后再判断当前这个点之前的连边是否为$train$ 如果是的话，那么给答案+1，否则不加。最后的 的结果就是$ans = k - ans$ 。但是比较奇怪的是，最开始使用一个数组 $istrain[i]$ 来记录 $i$ 点是否最短路是包括了 $train$ 边，最后也是统计被标记的个数。但是这样的做的结果是错误的。看了别人的题解好像是需要记录路径的长度。这里就不是很懂了。

不过话说回来太久没写最短路居然根本不会写了啊。。。

#include <cstdio>
#include <string>
#include<iostream>
#include<vector>
#include <stack>
#include <queue>
#include <map>
#include <cstdlib>
#include<string.h>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
typedef pair<int, int>pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;const int MAXN = 200000 + 10;
const int MAXM = 800000 + 10;struct Edge
{int u;int to;int next;bool t;ll cal;Edge(int _from = 0, int _to = 0, ll _cal = 0, bool _t = false, int _next = 0) :u(_from), to(_to), cal(_cal), t(_t), next(_next){}
}edge[MAXM];int head[MAXN], tot;
ll dis[MAXN];
bool vis[MAXN],vis1[MAXN];
bool istrain[MAXN];
int path[MAXN];void addedge(int u, int v, ll cal, bool t)
{edge[tot].to = v;edge[tot].cal = cal;edge[tot].t = t;edge[tot].next = head[u];head[u] = tot++;
}void init()
{memset(head, -1, sizeof head);memset(istrain, false, sizeof istrain);tot = 0;
}struct cmp
{bool operator()(const pair<int, pil> &x, const pair<int, pil> &y){if(x.second.second!=y.second.second)return x.second.second > y.second.second;return x.first > y.first;}
};
int ans = 0;
void dij()
{priority_queue<pair<int, pil>, vector<pair<int, pil>>, cmp>pq;for (int i = 0; i < MAXN; i++)dis[i] = (ll)1000000000*(ll)100000+50;pq.push(pair<int, pil>(0,pil(1,0)));dis[1] = 0;while (!pq.empty()){pair<int, pil> tmp = pq.top();pq.pop();if (vis[tmp.second.first])continue;vis[tmp.second.first] = true;if (tmp.first)ans++;int u = tmp.second.first;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (vis[v])continue;ll w = edge[i].cal;bool train = edge[i].t;if ((dis[v] >= dis[u] + w)){dis[v] = dis[u] + w;pq.push(pair<int,pil>(train,pil(v, dis[v])));}}}
}int main()
{int n, m, k;scanf("%d%d%d", &n, &m, &k);init();memset(istrain, false, sizeof istrain);for (int i = 0; i < m; i++){int u, v;ll wei;scanf("%d%d%I64d", &u, &v, &wei);addedge(u, v, wei, false);addedge(v, u, wei, false);}for (int i = 0; i < k; i++){int u, v;ll wei;scanf("%d%I64d", &v, &wei);addedge(1, v, wei, true);addedge(v, 1, wei, true);}ans = 0;dij();//for (int i = 1; i <= n; i++)if (istrain[i])ans++;//ans = k - ans;printf("%d\n", k-ans);//system("pause");
}