Code: Select all
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
const int INFL = 0x7fffffff / 2 - 1; // infinity
typedef pair<int, int> path;
typedef struct
{
int v; // neighboring vertex
int weight; // edge weight
} edge;
typedef struct
{
vector<int> degree; // outdegree of each vertex
vector<vector <edge> > edges; // adjacency info
int nedges; // number of edges in the graph
int nvertices; // number of vertices in the graph
} graph;
int *dist; // distance from start
int *parent; // discovery relation
stack<int> st; // auxiliary
void find_path (int start, int end, int parents[])
{
if ((start == end) || (end == -1)) st.push(start);
else
{
st.push(end);
find_path (start, parents[end], parents);
}
}
void insert_edge (graph * g, int x, int y, bool directed, int w)
{
edge ae; // auxiliary edge
int i; // counter
vector <edge> av; // auxiliary vector
while (x > g->nvertices || y > g->nvertices)
{
g->degree.push_back (0);
g->edges.push_back (av);
g->nvertices++;
}
for (i = 0; i < g->degree[x]; i++)
if (g->edges[x][i].v==y) break;
if (i == g->degree[x])
{
g->degree[x]++;
g->edges[x].push_back (ae);
g->edges[x].back ().v = y;
g->edges[x].back ().weight = w;
if (directed == false) insert_edge (g, y, x, true, w);
else g->nedges++;
}
}
void read_graph (graph * g)
{
bool fst; // first vertex
char line[80]; // input
int i, j; // counters
int len; // length
int n; // number of lines to read
int x, y, z=0; // auxiliary
vector <edge> av; // auxiliary vector
g->edges.clear ();
g->degree.clear ();
g->nedges = 0;
g->nvertices = 0;
g->degree.push_back (0);
g->edges.push_back (av);
scanf ("%d", &(g->nvertices));
dist = new int[26*27+1];
parent = new int[26*27+1];
for (i = 1; i <= g->nvertices; i++)
{
g->degree.push_back (0);
g->edges.push_back (av);
}
n = g->nvertices;
for (i = 1; i <= n; i++)
{
fst = true;
scanf("%s", line);
x = 26*(line[0]-'A') + 1;
len = strlen(line);
for (j = 2; j < len; j++)
if (islower(line[j]))
{
y = x + (line[j]-'a');
if (fst) fst = false;
else insert_edge (g, y, z, false, 1);
z = y;
}
else if (line[j] == '=')
{
j++;
y = 26*(line[j]-'A') + 1;
j++;
y += line[j]-'a';
insert_edge (g, y, z, false, 3);
}
}
}
void dijkstra (graph * g, int start)
{
bool intree[g->nvertices]; // is the vertex in the tree yet?
int i; // counters
int pr; // weight (priority)
int v; // current vertex to process
int w; // candidate next vertex
priority_queue<path, vector<path>, greater<path> > q;
for (i = 1; i <= g->nvertices; i++)
{
dist[i] = INFL;
intree[i] = false;
parent[i] = -1;
}
dist[start] = 0;
q.push (make_pair (0, start));
while (!q.empty())
{
pr = q.top().first;
v = q.top().second;
q.pop();
if (!intree[v])
{
intree[v] = true;
for (i = 0; i < g->degree[v]; i++)
{
w = g->edges[v][i].v;
q.push(make_pair(pr+g->edges[v][i].weight, w));
int sw = dist[v] + g->edges[v][i].weight;
if (dist[w] > sw)
{
dist[w] = sw;
parent[w] = v;
}
}
}
}
}
int main ()
{
char line[5], // input
route, // route
tmp; // temporary
graph g; // connection graph
int s, e; // start and end
read_graph (&g);
/*
for (int i=1; i<=g.nvertices; i++)
{
printf("%d:", i);
for (int j=0; j<g.degree[i]; j++) printf(" %d", g.edges[i][j]);
printf("\n");
}
*/
while (scanf("%s", line), line[0]!='#')
{
s = 26*(line[0]-'A') + (line[1] - 'a') + 1;
e = 26*(line[2]-'A') + (line[3] - 'a') + 1;
dijkstra (&g, s);
printf("%3d: ", dist[e]);
find_path (s, e, parent);
route=(st.top()-1)/26+'A';
putchar(line[0]);
while(!st.empty())
{
tmp=(st.top()-1)/26+'A';
if (tmp!=route)
{
route=tmp;
printf("=%c", route);
}
printf("%c", (st.top()-1)%26+'a');
st.pop();
}
printf("\n");
}
}
