【BUAA 1247】 最短路径问题
最短路径
没注明双向 傻傻的当成单向做的。。。。审题！！！
Dijkstra 模板题 代码如下
;typedef struct Edge{int d,p,v,next;}Edge;Edge eg[111111];int head[1111],tp;int dis[1111],cst[1111];bool vis[1111];int n,st,en;void Dijkstra(){memset(dis,INF,sizeof(dis));memset(cst,INF,sizeof(cst));memset(vis,0,sizeof(vis));int i,u,v,d,p,j;dis[st] = 0;cst[st] = 0;int w,pp,m;for(i = 0; i < n; ++i){pp = -1;w = m = INF;for(j = 1; j <= n; ++j){if(!vis[j] && (w > dis[j] || (w == dis[j] && m > cst[j]))){pp = j;w = dis[j];m = cst[j];}}if(pp == en) return;vis[pp] = 1;for(j = head[pp]; j != -1; j = eg[j].next){v = eg[j].v;d = eg[j].d;p = eg[j].p;if(!vis[v] && (dis[v] > dis[pp] + d || (dis[v] == dis[pp] + d && cst[v] > cst[pp] + p))){dis[v] = dis[pp] + d;cst[v] = cst[pp] + p;}}}}void Add(int u,int v,int d,int p){eg[tp].v = v;eg[tp].d = d;eg[tp].p = p;eg[tp].next = head[u];head[u] = tp++;}int main(){int m,i,u,v,d,p;while(~scanf(“%d %d”,&n,&m) && n){tp = 0;memset(head,-1,sizeof(head));for(i = 0; i < m; ++i){scanf(“%d %d %d %d”,&u,&v,&d,&p);Add(u,v,d,p);Add(v,u,d,p);}scanf(“%d %d”,&st,&en);Dijkstra();printf(“%d %d\n”,dis[en],cst[en]);}return 0;}
，一直开到梦的尽头。你曾经说，
