九度OnlineJudge之最短路径问题
解决：1004#include <iostream>#include <vector>using namespace std;typedef struct E{int next;int c;int cost;}E;bool mark[1001];int dis[1001];int cost[1001];vector<E> edge[1001];int main(){int N,M;while(cin>>N>>M){if (N==0&&M==0) break;for (int i=1;i<=N;i++){edge[i].clear();dis[i] = -1;mark[i] = false;cost[i] = 0;}while(M--){int a,b,c,cost;cin>>a>>b>>c>>cost;E T;T.c = c;T.cost = cost;T.next = b;edge[a].push_back(T);T.next = a;edge[b].push_back(T);}int S,D;cin>>S>>D;dis[S] = 0;mark[S] = true;int newP = S;//起点为S,for (int i=1;i<N;i++){for (int j=0;j<edge[newP].size();j++){E tmp = edge[newP][j];int t = tmp.next;int c = tmp.c;int co = tmp.cost;if (mark[t]==true) continue;if (dis[t]==-1 || dis[t] > dis[newP] +c || (dis[t]==dis[newP]+c) && (cost[t] >cost[newP] +co) ){dis[t] = dis[newP] + c;cost[t] = cost[newP] +co;}}int min=123123123;for (int j=1;j<=N;j++){if (mark[j]) continue;if (dis[j]==-1) continue;if (dis[j] < min){min = dis[j];newP = j;}}mark[newP] = true;} cout<<dis[D]<<" "<<cost[D]<<endl;}return 0;}
