const int MAXN = 1e2 + 5;
int a[N][N];
int dis[N];
int vis[N];
int n, m, s, t;
int x, y, v;
struct edge {
int to;//终点
int cost;//花费
edge(int x, int y) :to(x),cost(y) {}
};
typedef pair<int, int> P;//first为最短距离,second为定点编号。
vector<edge> graph[MAXN];
int dis[MAXN];
int path[MAXN];
int dij(int s)
{
memset(path, -1, sizeof(path));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<P, vector<P>, greater<P>> que;
que.push(P(0, s));
while (!que.empty())
{
P p = que.top();
que.pop();
int v = p.second;
if (dis[v] < p.first) continue;
for (int i = 0; i < graph[v].size(); i++)
{
edge e = graph[v][i];
if (dis[e.to] > dis[v] + e.cost)
{
dis[e.to] = dis[v] + e.cost;
que.push(P{ dis[e.to],e.to });
path[e.to] = v;
}
}
}
}