#include<iostream>
#include<map>
#include<queue>
#include<string.h>
#include<vector>
#include<string>
#include<algorithm>
#include <cstring>
using namespace std;
map<string, int> name;
struct Edge {
int weight;
int end, next;
Edge() {}
Edge(int e, int w, int n = 0) {
end = e;
weight = w;
next = n;
}
bool operator<(const Edge &a) const {
return (a.weight == weight ? end > a.end : weight > a.weight);
}
};
const int M = int(1e5 + 10);
const int INF = 0x3f3f3f3f;
const int N = 1001;
struct Gragh
{
Edge eg[M];
int cnt, head[N];
bool vis[N];
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int i, int j, int v) {
eg[cnt] = Edge(j, v, head[i]);
head[i] = cnt;
cnt++;
}
} gh1, gh2;
int path[N];
int dis[N];
void dijkstra(Gragh &gh, int src, int m) {
for (int i = 0; i <= m + 1; i++) {
dis[i] = INF;
}
memset(path, -1, sizeof(path));
dis[src] = 0;
path[src] = src;
priority_queue<Edge> q;
q.push(Edge(src, dis[src]));
while (!q.empty()) {
Edge f = q.top();
q.pop();
for (int i = gh.head[f.end]; i != -1; i = gh.eg[i].next) {
Edge &t = gh.eg[i];
if (dis[t.end] > f.weight + t.weight) {
dis[t.end] = f.weight + t.weight;
path[t.end] = f.end;
q.push(Edge(t.end, dis[t.end]));
}
}
}
}
#include<iostream>
#include<map>
#include<queue>
#include<string.h>
#include<vector>
#include<string>
using namespace std;
map<string, int>name;
double dis[1040];
int cnt, head[1040];
bool vis[1040];
struct Edge
{
double weight;
int end,next;
Edge() {}
Edge(int e,double w,int n)
{
end = e;
weight = w;
next = n;
}
};
Edge eg[1040];
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int i, int j, double v)
{
eg[cnt] = Edge(j, v, head[i]);
head[i] = cnt;
cnt++;
}
void SPFA(int src, int m)
{
for (int i = 0; i < m; i++)
{
dis[i] = vis[i] = 0;
}
queue<int>Q;
int q;
vis[src] = 1;
dis[src] = 1;
Q.push(src);
while (!Q.empty())
{
q = Q.front();
Q.pop();
vis[q] = 0;
for (int i=head[q];i!=-1;i=eg[i].next)
{
if (dis[eg[i].end] < dis[q] * eg[i].weight)
{
dis[eg[i].end] = dis[q] * eg[i].weight;
if (dis[src] > 1)
return;
if (!vis[eg[i].end])
{
vis[eg[i].end] = 1;
Q.push(eg[i].end);
}
}
}
}
}
