Descripción
En la era de la televisión, no mucha gente asiste a representaciones teatrales. Los antiguos comediantes de Malidinesia son conscientes de este hecho. Quieren propagar el teatro y, sobre todo, las comedias antiguas. Han impreso tarjetas de invitación con toda la información necesaria y con el programa. Muchos estudiantes fueron contratados para distribuir estas invitaciones entre la gente. Cada voluntario estudiantil ha asignado exactamente una parada de autobús y él o ella permanece allí todo el día y da invitación a las personas que viajan en autobús. Se realizó un curso especial donde los estudiantes aprendieron a influir en las personas y cuál es la diferencia entre influir y el robo.
El sistema de transporte es muy especial: todas las líneas son unidireccionales y conectan exactamente dos paradas. Los autobuses salen de la parada de origen con transeúntes cada media hora. Después de llegar a la parada de destino vuelven vacíos a la parada de origen, donde esperan hasta la siguiente media hora completa, por ejemplo X:00 o X:30, donde ‘X’ denota la hora. La tarifa para el transporte entre dos paradas se da por mesas especiales y se paga en el acto. Las líneas están previstas de tal manera, que cada viaje de ida y vuelta (es decir, un viaje que comienza y termina en la misma parada) pasa a través de una parada central de punto de control (CCS) donde cada pasajero tiene que pasar una revisión exhaustiva incluyendo la exploración del cuerpo.
Todos los miembros estudiantes de ACM salen del CCS cada mañana. Cada voluntario debe pasar a una parada predeterminada para invitar a los pasajeros. Hay tantos voluntarios como paradas. Al final del día, todos los estudiantes viajan de vuelta a CCS. Debe escribir un programa informático que ayude a ACM a minimizar la cantidad de dinero a pagar todos los días por el transporte de sus empleados.
Entrada
La entrada consta de casos N. La primera línea de la entrada solo contiene el entero positivo N. A continuación, siga los casos. Cada caso comienza con una línea que contiene exactamente dos enteros P y Q, 1 <= P,Q <= 1000000. P es el número de paradas incluyendo CCS y Q el número de líneas de autobús. Luego están las líneas Q, cada una describiendo una línea de autobús. Cada una de las líneas contiene exactamente tres números : la parada de origen, la parada de destino y el precio. El CCS se designa por el número 1. Los precios son enteros positivos, la suma de los cuales es menor que 10000000000. También puede asumir que siempre es posible pasar de cualquier parada a cualquier otra parada.
Salida
Para cada caso, imprima una línea que contenga la cantidad mínima de dinero a pagar cada día por ACM por los costos de viaje de sus voluntarios.
Entrada de muestra
2
0 p
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
Salida de muestra
46
210
Significado general
Hay n grupos de datos para cada dato de prueba, cada grupo de datos tiene dos números p y q, respectivamente, lo que indica que hay varios puntos y varios lados, y luego hay lados q, cada lado tiene tres El número, de, y el costo respectivamente representan el punto de partida, el punto final y el consumo. Pregunte el tiempo mínimo desde el punto de partida 1 a cada punto, y el tiempo mínimo de cada punto a 1, cuál es la suma total
Ideas específicas
Comience desde 1 para ejecutar el trazado más corto de una sola fuente mientras encuentra la distancia mínima dis de un punto a cada punto, luego invierta el diagrama, cambie las flechas y, a continuación, vuelva a ejecutar el trazado más corto para encontrar ¿Cuál es la distancia más corta de cada punto a 1? Agregue los valores de las dos matrices juntas para obtener la respuesta final
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
typedef long long int LLD;
const LLD Maxnum=1000005;
struct node
{
LLD from,to,cost;
}line[Maxnum];
vector<node>Line[Maxnum];
LLD dis[Maxnum],flag[Maxnum];
LLD spfa(LLD p)
{
fill(dis,dis+p+5,0x7fffffff);
memset(flag,0,sizeof(flag));
queue<LLD>dui;
dui.push(1);
flag[1]=1;
dis[1]=0;
while (!dui.empty())
{
LLD now=dui.front();
dui.pop();
flag[now]=0;
for (LLD i=0;i<Line[now].size();i++)
{
node next=Line[now][i];
if (dis[next.from]<0x7fffffff&&dis[next.to]>dis[next.from]+next.cost)
{
dis[next.to]=dis[next.from]+next.cost;
if (!flag[next.to])
{
dui.push(next.to);
flag[next.to]=1;
}
}
}
}
LLD ans=0;
for (LLD i=1;i<=p;i++)
{
ans+=dis[i];
}
return ans;
}
void init(LLD p)
{
for (LLD i=0;i<=p;i++)
{
Line[i].clear();
}
return ;
}
int main()
{
LLD n;
scanf("%lld",&n);
while (n--)
{
LLD p,q;
scanf("%lld %lld",&p,&q);
init(p);
for (LLD i=1;i<=q;i++)
{
LLD from,to,cost;
scanf("%lld %lld %lld",&line[i].from,&line[i].to,&line[i].cost);
node now;
now.from=line[i].from;
now.to=line[i].to;
now.cost=line[i].cost;
Line[now.from].push_back(now);
}
LLD ans=spfa(p);
init(p);
for (LLD i=1;i<=q;i++)
{
node now;
now.from=line[i].to;
now.to=line[i].from;
now.cost=line[i].cost;
Line[now.from].push_back(now);
}
ans+=spfa(p);
printf("%lldn",ans);
}
return 0;
}
.
