Это мое решение, чтобы решить в O (N) Графы: #include #include #include
typedef long long ll;
void fs_int(int *x) {
register int c = getchar_unlocked();
*x = 0;
int neg = 0;
for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
if(c=='-') {
neg = 1;
c = getchar_unlocked();
}
for(; c>47 && c<58 ; c = getchar_unlocked()) {
*x = (*x<<1) + (*x<<3) + c - 48;
}
if(neg)
*x = -(*x);
}
typedef struct {
int next;
int val;
int d;
}List;
typedef struct
{
int parent;
int shrt;
ll count;
int on_reg;
int ch;
} Node;
#define MOD 1000000007
ll get_sum(Node *tr,List *l)
{
Node *t, *t2;
int i,j,n=0,fix;
ll result;
static int *reg=NULL,sz=1000;
if (!reg)
reg=malloc(sizeof(int)*sz);
reg[n++]=1;
int cur_d;
while(n)
{
///fix is the limit for the for, it is the shortname of "for ix" :
// from 0 to fix there are the old values, from fix to n there are the new ones
fix=n;
for (i=0;i<fix;i++)
{
//the better way to reduce the complexity is shift the last item to the current one
t=&tr[reg[i]];
reg[i--]=reg[--fix];
reg[fix]=reg[--n];
t->on_reg=0;
///this scores all the edges from departing from this node
///the criteria to avoid propagation is the key of the program
for (j=t->ch;j;j=l[j].next)
{
if (l[j].val==1) //avoid the root
continue;
t2=&tr[l[j].val]; //store in some comfortable variable
cur_d=t->shrt+l[j].d;
if (t2->shrt!=0 && t2->shrt< cur_d) ///if my path is heaviest nothing to do
continue;
else if (t2->shrt ==cur_d) //I found an item with same weight. It was required to count them
t2->count++;
else if (t2->shrt==0 || t2->shrt>cur_d) //found a unexplored item or my path is lighter
{
t2->shrt=cur_d;
t2->count=1;
if (!t2->on_reg) //if not already in the reg, I insert it inside
{
if (n>=sz)
{
sz<<=1;
reg=realloc(reg, sizeof(int)*sz);
}
reg[n++]=l[j].val; //at position n
t2->on_reg=1;
}
}
}
/* printf ("reg: ");
for (k=0;k<n;k++)
printf ("%d ",reg[k]);
printf ("\n");*/
}
}
//printf ("\n");
return result;
}
typedef long long ll;
void set_depth(Node *tr, List *l, int rt,int cd,int parent)
{
int i;
tr[rt].parent=parent;
for (i=tr[rt].ch;i;i=l[i].next)
if (l[i].val== parent)
continue;
else
set_depth(tr,l,l[i].val,cd+1,rt);
}
int main()
{
int t,n,q,i,u,v,d;
fs_int(&t);
int il=1;
Node tr[100005];
List l[200005];
List *tl;
while (t--)
{
fs_int(&n);
fs_int(&q);
il=1;
memset(tr,0,sizeof(tr));
memset(l,0,sizeof(l));
for (i=0;i<q;i++)
{
fs_int(&u);
fs_int(&v);
fs_int(&d);
tl=&l[il];
tl->next=tr[u].ch;
tl->val=v;
tl->d=d;
tr[u].ch=il++;
tl=&l[il];
tl->next=tr[v].ch;
tl->val=u;
tl->d=d;
tr[v].ch=il++;
}
//set_depth(tr,l,1,0,0);
// print(tr,l,1,0,0);
get_sum(tr,l);
ll res=1;
for (i=2;i<=n;i++)
{
res= ((res%MOD) *(tr[i].count%MOD))%MOD;
}
printf ("%lld\n",res);
}
return 0;
}
функция Вас интересует функция get_sum(). Это первый поиск по ширине, который в графе означает проверку вдоль концентрических кругов, что позволяет избежать бесполезных распространения. Он сохраняет значения в этом виртуальном круге, на массиве, называемом reg. И на каждом шагу вы будете проверять вперед. О эффективности, которую вы можете проверить сами по себе на конкурсе Ways. Он имеет одно из лучших времен
Это ужасно плохая идея: ['#include'] (http://stackoverflow.com/questions/31816095/why-should-i-not -include-bits-stdc-h) ['using namespace std;'] (http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Вместе они делают две вещи: 1. Потяните всю стандартную библиотеку в глобальное пространство имен, оставляя вас с удивительным минным полем именных столкновений и молчащих замен, и 2. получите свое резюме и портфолио, брошенное в круглый файл. Только не делай этого. –
user4581301
На более сразу полезном фронте, пожалуйста, предоставьте набор входов, которые приводят к неудачной реализации. Делает отладку проще. Если это не из-за огромного размера, подумайте об использовании отладчика, который почти наверняка появился с вашим отладчиком. – user4581301
вы не изменили посещаемый узел источника. Исходный узел должен быть отмечен как посещенный до ввода цикла while. –