思路:用向量建立图(向量二维数组)。然后用Dijkstra算法求出最佳解。
用到自定义的结构体优先队列。
u为本结点,v为相连结点,d为距离,m为花费。
注意本题的图是无向图。
#include <iostream> #include <queue> #include <vector> #define MAXN 100000000 #define MAX 100001 using namespace std; struct rout { int u;//本结点 int d; //距离 int m;//花费 int v;//相连结点 friend bool operator >(rout node1,rout node2)//自定义结构体优先队列 { if (node1.d == node2.d) { return node1.m > node2.m; } return node1.d > node2.d; } }r[1001], temp; bool done[1001];//标记是否访过 vector<struct rout>first[MAX]; int main() { int n, m, s, t, i, flag; while (cin>>n>>m && (n||m)) { memset(done, 0, sizeof(done)); for (i=1; i<=m; i++) { cin>>temp.u>>temp.v>>temp.d>>temp.m; first[temp.u].push_back(temp);//交换两个顶点的值,建立无向图 flag = temp.u; temp.u = temp.v; temp.v = flag; first[temp.u].push_back(temp); } cin>>s>>t; //开始,结束 for (i=1; i<=n; i++) { r[i].d = MAXN; r[i].m = MAXN; } r[s].d = r[s].m = 0; r[s].u = r[s].v = s; priority_queue<rout, vector<rout>, greater<rout> >q; q.push(r[s]); while (!q.empty()) { struct rout j = q.top(); q.pop(); int x = j.u; if (done[x]) continue; done[x] = 1; if (x==t) { cout<<j.d<<" "<<j.m<<endl; break; } for (i=0; i<first[x].size(); i++) { int n = first[x][i].v; if (r[n].d>=r[x].d+first[x][i].d)//花费相等时也要进行更新 { r[n].d = r[x].d + first[x][i].d; r[n].m = r[x].m + first[x][i].m; r[n].u = n; q.push(r[n]); } } } for (i=1; i<=n; i++)//定义的vector很大,只能定义为全局变量,进行清空为了下一次能使用 first[i].clear(); } return 0; }