I Wanna Go Home
传送门：http://acm.pku.edu.cn/JudgeOnline/problem?id=3767
这道题目，真不爽......开始是两边dijkstra处理的，用一个for循环，连接两个camp
，结果忘记了一个很致命的疏忽： 就是比如 从 1阵营 到 2 阵营，1(1)->7(2)-->2(2)，没有保证 1-->7是最短的
只是保证了在所有的1阵营中，1到其他的点是最短的，也是我wa了好多次的原因。
更郁闷的是，RE出现了好多次，结果程序反复写了好几次，纠结的是，有的程序用C++提交 RE，用G++提交 Wa。
偶的天........哎，代码如下：
#include <iostream>
using namespace std;
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int N=605;
const int INF=20000000;
int n,m;
int dist[N];
int b[N];
int map[N][N];
bool used[N];
bool init()
{
int i,j;
scanf("%d",&n);
if(n==0) return false;
for(i=1;i<=n;i++)
used[i]=false;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)map[i][j]=INF;
else map[i][j]=0;
scanf("%d",&m);
int s,e,v;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&s,&e,&v);
if(map[s][e]>v) map[s][e]=map[e][s]=v;
}
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
return true;
}
void solve()
{
int i,j,k,min;
for(i=1;i<=n;i++)
dist[i]=map[1][i];
used[1]=true;
for(i=1;i<=n;i++)
{
min=INF;
k=1;
for(j=1;j<=n;j++)
if(!used[j]&&dist[j]<min)
min=dist[j],k=j;
// if(min==INF) break;
used[k]=true;
for(j=1;j<=n;j++)
if(!used[j]&&dist[k]+map[k][j]<dist[j])
if(!(b[k]==2&&b[j]==1))
dist[j]=dist[k]+map[k][j];
}
/* for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%10d",map[i][j]);
cout<<endl;
}
for(i=1;i<=n;i++)
cout<<dist[i]<<" ";
cout<<endl;
*/
if(dist[2]>=INF) printf("-1/n");
else printf("%d/n",dist[2]);
}
int main()
{
//freopen("1.in","r",stdin);
while(init())
{
solve();
}
return 1;
}
还有郁闷的，就是freopen前面没加两个斜杠，结果贡献了两个 WA，再郁闷。
提交发现 是 0MS，吼吼~~~~~