这道题是增加了一个花费的数据。。不过也不是大问题。。
不过最大问题是、这题的最坑爹之处。默认的测试数据里包含两个城市间有多条路径的情况。啊啊啊。。
这TM的研究生复试上机考试,会坑死一群奋斗了一年的倒霉的孩纸额。。。
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXV=1005;
struct vertex
{
int d;
int p;
};
vertex cost[MAXV][MAXV];
vertex operator+(const vertex&a,const vertex&b)
{
vertex c;
c.d=a.d+b.d;
c.p=a.p+b.p;
return c;
}
void Dijkstra(int n,int v,int t)
{
vertex dist[MAXV];
bool s[MAXV];
for(int i=1;i<=n;i++)
{
dist[i]=cost[v][i];
s[i]=0;
}
s[v]=1;
int k;
for(int i=1;i<=n;i++)
{
int min=INF;
for(int j=1;j<=n;j++)
{
if(s[j]==0&&dist[j].d<min)
{
k=j;
min=dist[j].d;
}
}
s[k]=1;
for(int j=1;j<=n;j++)
{
if(s[j]==0)
{
if(cost[k][j].d<INF&&dist[k].d+cost[k][j].d<dist[j].d)
dist[j]=dist[k]+cost[k][j];
else if(dist[k].d+cost[k][j].d==dist[j].d)
if(dist[k].p+cost[k][j].p<dist[j].p)
dist[j].p=dist[k].p+cost[k][j].p;
}
}
}
printf("%d %d\n",dist[t].d,dist[t].p);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cost[i][j].d=cost[i][j].p=INF;
}
}
int a,b,d,p;
while(m--)
{
scanf("%d%d%d%d",&a,&b,&d,&p);
if(cost[a][b].d!=INF&&cost[a][b].d>d)
{
cost[a][b].d=cost[b][a].d=d;
cost[a][b].p=cost[b][a].p=p;
}
else if(cost[a][b].d==INF)
{
cost[a][b].d=cost[b][a].d=d;
cost[a][b].p=cost[b][a].p=p;
}
}
int v,t;
scanf("%d%d",&v,&t);
Dijkstra(n,v,t);
}
return 0;
}
分享到:
相关推荐
浙大计算机研究生复试上机考试源码,含有浙大计算机研究生复试上机考试源码
浙大计算机研究生复试上机考试——历年题目(2005-2008)
浙大研究生复试上机试题(2005-2008)
浙大2005-2009年复试上机题,希望能对考研的朋友有所帮助
浙大复试上机试题2005-2009 浙大复试上机试题2005-2009 浙大复试上机试题2005-2009
上海交大考研复试上机试题,以及历年答案,打算保研或考研到浙大计算机的同学必读
浙江大学计算机复试题解和上机题解,有复试的各个科目,和上机的题目。
浙大计算机学院考研复试上机试题及参考答案.doc
计算机考研复试上机集锦 含有:同济大学 浙江大学 上海交通
浙大计算机学院考研复试上机试题与参考答案.doc
浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试常问问题浙大计算机软件复试...
浙江大学城市学院C语言期末上机考试题库
浙大上机资料,内含统计字符游船出租等常见问题的详解
浙大计算机复试上机考试题及答案!
浙大计算机类考研,包括计算机学院的计算机系和软件学院等,上机考试题目,有详细答案和测试用例,考试要求等.
浙大的研究生课程计算机视觉课件,2011-2012学年
浙江大学大学计算机基础 2010-12-模拟卷及答案.docx
最近浙大上机复试相关内容,希望对各位有帮助。。
本程序是为浙江大学研究生公共英语水平考试自测模拟题集做的一个答题小程序,可以显示答题记录,记录答题时间,自动核对答案,显示答题错误的题目,计算答题分数等,并可以将所有答题信息保存为txt文档,方便日后...
收集的几所高校的研究生复试上机题 上交大05-07 山大07、09 华科06、07 浙大05-09 交大08