T122393 À la Volonté du Peuple

题目链接

题目大意：

给一个有边权的无向图，有自环，有重边。一个火从1点开始烧，烧完之后就变成了灰烬（也就是火不能两次到达1点）火会延续到没有烧过的边，两个火苗相遇的时候会爆炸，
问爆炸的次数。
这个题，，哎 我又菜了。
想到了最短路，但是一直想着不是除了最短路的那棵树的边以外其余的边不都爆炸一次吗。但是 我错了，， 错了
题解
分为点上爆炸和边上爆炸，
点上爆炸的情况：只要1为源点最短路中这个点有两个前驱点（这两个点到这个点都是最短路），这个点就会爆炸。
边上爆炸的情况：非最短路边都会爆炸
害~
代码

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 3e5+5;
struct Edge{
   
	int id;
	int val;
	int next;
	bool operator< (const Edge& a)const{
   
		return val > a.val;
	}
}edge[2000006];
int head[maxn];
int visp[maxn];
int cnt ;
void add(int x,int y,int val)
{
   
	edge[cnt].id = y;
	edge[cnt].val = val;
	edge[cnt].next = head[x];
	head[x] = cnt ++ ;
}
int vis[maxn];
int dis[maxn];
priority_queue<Edge> qq;
int main()
{
   
	int n,m;
	scanf("%d%d",&n,&m);
	cnt = 0;
	for (int  i= 1; i <= n; i ++ )
	{
   
		head[i] = -1;
		dis[i] = 0x3f3f3f3f;
	}
	int ans = 0;
	for (int i = 1; i <= m;  i++ )
	{
   
		int x,y,val;
		scanf("%d%d%d",&x,&y,&val);
		add(x,y,val);
		if(x != y)
		add(y,x,val);
	}
	Edge t;
	t.id = 1;
	t.val = 0; 
	qq.push(t);
	dis[1] = 0;
	while(!qq.empty())
	{
   
		Edge t = qq.top();
		qq.pop();
// printf("%d\n",t.val);
		int tt = t.id;
		if(vis[tt])
			continue;
		vis[tt] = 1;
// printf("%d\n",dis[tt]);
		for (int i = head[tt]; ~i ; i = edge[i].next)
		{
   
			int x = edge[i].id;
			if(vis[x] == 0 && dis[x] > dis[tt] + edge[i].val)
			{
   
				dis[x] = dis[tt] + edge[i].val;
				Edge p;
				p.id =x;
				p.val = dis[x];
				qq.push(p);
			}
		}
	}
	for (int i = 1; i <= n; i ++ )
	{
   
		int ss =0 ;
		for (int j = head[i]; ~j; j = edge[j].next)
		{
   
			int x = i, y = edge[j].id;
// printf("%d %d\n",x,y);
			if(dis[x] == dis[y] + edge[j].val) ss ++ ;
			else if(y >= x && dis[y] < dis[x] + edge[j].val && dis[x] < dis[y] + edge[j].val) ans ++ ;
		}
		if(ss > 1)
			ans ++ ;
	}
	printf("%d\n",ans);
}